#include <stdio.h>
#include <stdlib.h>
#include <locale.h>

#define OK 1
#define ERROR 0
#define Max_Int 32726
#define MVNum 100
 
typedef int Status;
typedef int ArcType;
typedef char VerTexType;
 
struct ed{
    VerTexType Head;//边的始点
    VerTexType Tail;//边的终点
    ArcType lowcost;//边的权值
}Edge[MVNum];
 
typedef struct{
    VerTexType vex[MVNum];//顶点表
    ArcType arc[MVNum][MVNum];//邻接矩阵
    int arcnum, vexnum;//顶点数和边数
}AMGraph;

//****************************************

int LocateVex(AMGraph *G, VerTexType v)//下标位置的查找
{
    int i;
    for (i = 0; i < G->vexnum; i++)
    {
        if (G->vex[i] == v)
            return i;
    }
    return -1 ;
}

/***************************************
void DispGraph (AMGraph &G)
{   
    int i , j ;
    printf ("~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
    printf ("\n输出邻接矩阵的信息：\n\n");

    for (i = 0 ; i<G.arcnum ; i++);
        printf ("%9d",G.vex[i]);
    printf ("输出邻接矩阵：\n");

    for(i=0;i<G.arcnum;i++)
        {
            for(j=0;j<G.arcnum;j++)
                {
                if(G.arc[i][j]==Max_Int)
                    printf("%8s", "0");
                else
                    printf("%8d",G.arc[i][j]);
                }
        printf("\n");   
    }
}

//***************************************/
 
Status CreateUDN(AMGraph *G)//创建无向网
{
    printf ("建设 1.上海、2.北京、3.南京、4.扬州、5.南通、6.苏州等 六城市之间的交通线路（数字即为城市代号）：\n");

    VerTexType v1, v2;
    ArcType w;//w为权值即建设费用
    int i, j, k;
    printf("输入总城市数、总拟定的路数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    printf("输入各个城市代号值：");
        fflush(stdin);
    for (i = 0; i < G->vexnum; i++)
    {
        scanf("%c", &G->vex[i]);
    }
    for (i = 0; i < G->vexnum; i++)
        for (j = 0; j < G->vexnum; j++)
            {
                G->arc[i][j] = Max_Int;  //将各值置位无穷大
            }
    for (k = 0; k < G->arcnum; k++)
    {
        fflush(stdin) ;
        printf("依次输入相连道路两个城市代号以及建路的费用：");
        scanf("%c %c %d", &v1, &v2, &w);
        Edge[k].Head = v1;
        Edge[k].Tail = v2;
        Edge[k].lowcost = w;
        i = LocateVex(G, v1);//查找该城市代号在总的数组中的位置
        j = LocateVex(G, v2);
        G->arc[i][j] = w;  //相应的俩城市之间的道路建设费用
        G->arc[j][i] = G->arc[i][j];//无向图故而两城市之间道路互通
    }


    return OK;
}

//*******************************************************

void Sort(AMGraph &G) //将所输入的两城市代码以及建设费用按费用进行排序
{
    int i, j, addr;
    ArcType min;
    ed temp;//定义结构体temp
    for (i = 0; i < G.arcnum; i++)
    {
        min = Edge[i].lowcost;  //将第一个权值赋值给min
        addr = i;
        for (j = i + 1; j < G.arcnum; j++)
        {
            if (min>Edge[j].lowcost)  //不断的比较互换
            {
                min = Edge[j].lowcost;
                addr = j;
            }//将最小权值换位到i的位置
        }
        if (addr != i)//若符合整个结构体进行位置互换
        {
            temp = Edge[i];
            Edge[i] = Edge[addr];
            Edge[addr] = temp;
        }
    }
}

//*******************************************************


void MiniSpanTree_Kruskal(AMGraph &G)//应用Kruskal算法进行建立
{
    int i, j,v1,v2,vs1,vs2;//vs1 vs2表示连通分量
    int sum=0 , k=0;
    int Vexset[MVNum];
    ed rets[MVNum] ;
    Sort(G);
    for (i = 0; i < G.vexnum; ++i)
        Vexset[i] = i;
    printf ("最经济方案为：\n");
    for (i = 0; i < G.vexnum;++i)
    {
        v1 = LocateVex(&G, Edge[i].Head);//v1为始点的下标
        v2 = LocateVex(&G, Edge[i].Tail);//v2为终点的下标
        vs1 = Vexset[v1];
        vs2 = Vexset[v2];
        if (vs1 != vs2)//边的连个顶点分属两个不同的连通分量
        {
            printf("%c->%c--%d\n", Edge[i].Head, Edge[i].Tail ,Edge[i].lowcost);
            for (j = 0; j < G.vexnum; ++j)
                if (Vexset[j] == vs2)
                    Vexset[j] = vs1;
            sum += Edge[i].lowcost ;
        }
        
    }
    printf ("最经济方案费用为：%d\n",sum);
}


int main()
{
    AMGraph G;
    CreateUDN(&G);
/*    DispGraph (G) ;
    for (i=0 ; i<G.arcnum ;i++)
        for (j=0 ; j<G.arcnum ;j++)
            if (G.arc[i][j]==Max_Int)
                printf ("0");
            else
                printf ("%d",G.arc[i][j]);*/
    MiniSpanTree_Kruskal(G);
    return 0;
}