Problem Description

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N 行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。

Output

对每个测试用例，在1行里输出

全省畅通需要的最低成本。若

统计数据不足以保证畅通，则输出“?”。

Sample Input

3 3

1 2 1

1 3 2

2 3 4

1 3

2 3 2

0 100

Sample Output

3

?

解题思路：

全省畅通也就是求

最小生成树，如果给出的数据不全，得到的将是INF，此时输出'?'，否则输出对应的最小代价。

AC代码之Prim算法：

1 #include
       
         2 using namespace std; 3 const int INF = 0x3f3f3f3f; 4 int m,n,a,b,c,mincost[105],cost[105][105]; 5 bool vis[105]; 6 void Prim(){ 7     for(int i=1;i<=n;++i) 8         mincost[i]=cost[1][i]; 9     mincost[1]=0;vis[1]=true;10     int res=0;11     for(int i=1;i
        
         mincost[j]))k=j;15         if(k==-1)break;16         if(mincost[k]==INF)break;//如果此时的最小值还是INF，说明统计数据不足，直接退出17         vis[k]=true;18         res+=mincost[k];19         for(int j=1;j<=n;++j)20             if(!vis[j])mincost[j]=min(mincost[j],cost[k][j]);21     }22     bool flag=false;//标记是否还有未访问23     for(int i=1;i<=n;++i)24         if(!vis[i]){flag=true;break;}//如果还有未被访问，说明统计数据不全，输出'?'25     if(flag)cout<<'?'<
         
          >m>>n && m){31         memset(vis,false,sizeof(vis));32         for(int i=1;i<=n;++i)33             for(int j=1;j<=n;++j)34                 cost[i][j]=(i==j?0:INF);35         for(int i=1;i<=m;++i){36             cin>>a>>b>>c;37             cost[a][b]=cost[b][a]=c;38         }39         Prim();40     }41     return 0;42 }
         
        
       

 AC之Kruskal算法（并查集）：判断数据不全的依据是如果所有节点的根节点不一样，即不在同一个集合时输出'?'，否则输出最小代价即可。

1 #include
       
         2 using namespace std; 3 int m,n,father[105],sum; 4 struct edge{
     int u,v,cost;}es[5000];//可能有n*(n-1)/2条边，因为这是无向有权图，此时开5000长度已经够了 5 bool cmp(const edge& e1,const edge& e2){
     //引用，减少拷贝所花时间 6     return e1.cost
        
         >m>>n && m){26         for(int i=1;i<=m;++i)27             scanf("%d %d %d",&es[i].u,&es[i].v,&es[i].cost);28         sort(es+1,es+m+1,cmp);//权值按从小到大排序29         sum=0;init_union_find();//初始化30         for(int i=1;i<=m;++i)31             unite(es[i].u,es[i].v,es[i].cost);32         bool flag=false;33         for(int i=2;i<=n;++i)//判断是否在同一个集合中34             if(find_father(1)!=find_father(i)){flag=true;break;}35         if(flag)cout<<'?'<