本文共 2430 字，大约阅读时间需要 8 分钟。

Description

当前农村公路建设正如火如荼的展开，某乡镇政府决定实现村村通公路，工程师现有各个村落之间的原始道路统计数据表，表中列出了各村之间可以建设公路的若干条道路的成本，你的任务是根据给出的数据表，求使得每个村都有公路连通所需要的最低成本。

Input

连续多组数据输入，每组数据包括村落数目N(N <= 1000)和可供选择的道路数目M(M <= 3000)，随后M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个村庄的编号和修建该道路的预算成本，村庄从1～N编号。

Output

输出使每个村庄都有公路连通所需要的最低成本，如果输入数据不能使所有村庄畅通，则输出-1，表示有些村庄之间没有路连通。

Sample

Input

5 81 2 121 3 91 4 111 5 32 3 62 4 93 4 44 5 6

Output

19

答案：

最小生成树Prim算法：

#include 
   
    #include
    
     #define ll long long#define INF 0x3f3f3f3fconst int N = 1e5 + 10;using namespace std;int mp[1111][1111];int vis[1111];int Prim(int n){       int i;    int j;    int dp[1111];    int sum;    int minn;    int flag;    for(i = 1; i<= n; i++)    {           vis[i] = 0;        dp[i] = mp[1][i];    }    vis[1] = 1;    sum = 0;    for(i =1; i < n; i++)    {           minn = INF;        flag = -1;        for(j = 1; j<= n; j++)        {               if(!vis[j] && dp[j] < minn)            {                   minn = dp[j];                flag = j;            }        }        if(minn == INF)            return -1;        vis[flag] = 1;        sum += minn;        for(j = 1; j<= n; j++)        {               if(!vis[j] && dp[j] > mp[flag][j])                dp[j] = mp[flag][j];        }    }    return sum;}int main(){       ios::sync_with_stdio(0);    int n,m;    while(cin>>n>>m)    {           int i,j;        for(i=1; i<=n; i++)        {               for(j=1; j<=n; j++)            {                   if(i==j)                    mp[i][j]=0;                else                    mp[i][j]=INF;            }        }        while(m--)        {               int x,y,k;            cin>>x>>y>>k;            if(k
    
   

最小生成树Kruskal算法（并查集思想）

#include 
   
    #include
    
     #define ll long long#define INF 0x3f3f3f3fconst int N = 1e5 + 10;using namespace std;struct node{       int u,v,w;} dp[1111];int n;int vis[1111];bool cmp(node a,node b){       return a.w
     
      >n>>m)    {           init();        for(int i=1; i<=m; i++)        {               cin>>dp[i].u>>dp[i].v>>dp[i].w;        }        sort(dp+1,dp+1+m,cmp);        int ans=0,cnt=0;        for(int i=1; i<=m; i++)        {               if(cnt==n-1)            {                   break;            }            if(!Merge(dp[i].u,dp[i].v))            {                   ans=ans+dp[i].w;                cnt++;            }        }        if(cnt==n-1)        {               cout<
      
       <
      
     
    
   

最小生成树算法链接：