08-图7 公路村村通 (30 分)

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式:

输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。

输出格式:

输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。

输入样例:

6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

输出样例:

12

Code

#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 1001 /* 最大顶点数设为100 */
#define MaxDist 250000 /* 不可能达到的最长路径 */
typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
typedef int ValueType;

/* 边的定义 */
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;      /* 有向边<V1, V2> */
    ValueType Value;
};
typedef PtrToENode Edge;

/* 邻接点的定义 */
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
    Vertex AdjV;        /* 邻接点下标 */
    ValueType Value;
    PtrToAdjVNode Next;    /* 指向下一个邻接点的指针 */
};

/* 顶点表头结点的定义 */
typedef struct Vnode{
    PtrToAdjVNode FirstEdge;/* 边表头指针 */
} AdjList[MaxVertexNum];    /* AdjList是邻接表类型 */

/* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;     /* 顶点数 */
    int Ne;     /* 边数 */
    AdjList G;  /* 邻接表 */
};
typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */

/*全局变量声明*/
int dist[MaxVertexNum+1];

LGraph CreatGraph(int VexterNum);
LGraph BuildGraph(int VexterNum,int EdgeNum);
void InsertEdge(LGraph Graph,Edge E);
int Prim(LGraph Graph,Vertex S);
Vertex FindMindist(int Num);


int main()
{
    int N,M,Charge;
    scanf("%d %d",&N,&M);
    LGraph Graph = BuildGraph(N,M);
    Vertex V;

// {
// /*test1:邻接表是否建立成功*/
// PtrToAdjVNode W;
// for(V=1;V<=N;V++)
// {
// for(W = Graph->G[V].FirstEdge;W;W = W->Next)
// printf("%d ",W->AdjV);
// printf("\n");
// }
// }


    /*初始化disk数组为无穷大*/
    for(V=0;V<N+1;V++) dist[V] = MaxDist;

    Charge = Prim(Graph,1);
    printf("%d",Charge);

    return 0;
}
/*创建一个没有边的初始空图*/
LGraph CreatGraph(int VexterNum)
{
    LGraph Graph;
    Graph = (LGraph)malloc(sizeof(struct GNode));
    Graph->Ne = 0;
    Graph->Nv = VexterNum;
    for(int V=1;V<=Graph->Nv;V++)
    {
        Graph->G[V].FirstEdge = NULL;
    }
    return Graph;
}

/*建立完整图，插入边及权重以及结点数据等*/
LGraph BuildGraph(int VexterNum,int EdgeNum)
{
    LGraph Graph = CreatGraph(VexterNum);
    Graph->Ne = EdgeNum;
// printf("Graph->Nv = %d,Graph->Ne = %d\n",Graph->Nv,Graph->Ne);
    Edge E;
    E = (Edge)malloc(sizeof(struct ENode));
    for(int i=0;i<Graph->Ne;i++)
    {
        scanf("%d %d %d",&E->V1,&E->V2,&E->Value);
        InsertEdge(Graph,E);
    }
// printf("build success\n");
    return Graph;
}

/*插入边*/
void InsertEdge(LGraph Graph,Edge E)
{
    PtrToAdjVNode NewNode;

    //V1->V2,将V2邻接点插入到V1为下标到链表中
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V2;
    NewNode->Value = E->Value;
    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;

    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V1;
    NewNode->Value = E->Value;
    NewNode->Next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}

/*Prim算法，贪心算法*/
int Prim(LGraph Graph,Vertex S)
{
    Vertex V;
    PtrToAdjVNode W;
    int Charge=0;
    dist[S]=0;
    for(W = Graph->G[S].FirstEdge;W;W = W->Next) dist[W->AdjV] = W->Value;
    while(1)
    {
        V = FindMindist(Graph->Nv);
        if(V==0) break;
        Charge += dist[V];
        dist[V]=0;
// printf("dist[%d] = %d,Charge = %d\n",V,dist[V],Charge);
        for(W = Graph->G[V].FirstEdge;W;W = W->Next)
        {
            if(dist[W->AdjV]!=0)
            {
                if(W->Value<dist[W->AdjV])
                {
                    dist[W->AdjV] = W->Value;
// printf("dist[%d] = %d\n",W->AdjV,dist[W->AdjV]);
                }
            }
        }
    }

    for(V=1;V<=Graph->Nv;V++)
    {
        if(dist[V]!=0)
        {
            Charge = -1;
            break;
        }
    }
    return Charge;

}

/*未收录顶点dist最小者*/
Vertex FindMindist(int Num)
{
    Vertex V,Min=0;
    for(V=1;V<=Num;V++)
    {
        if(dist[V]&&dist[V]<dist[Min]) Min = V;
    }

    return Min;
}