畅通工程（kruskal算法）

个人心得：日了狗，WR了俩个小时才发现是少了个vector清理，我也是醉了，不过后面还是对这个有了更好得了解，一是我得算法，而是学长改进

后的算法，改进后得算法还要判断所有村庄是否在连在一起，其实我觉得实必要性不大。

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

 

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
?

 

Source

浙大计算机研究生复试上机考试-2007年

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<vector>

 #include<algorithm>

 using namespace std;

 const long long maxa=;

 int n,m;

 struct village

 {

     int v;

     int e;

     int w;

     village(int x,int y,int z){

             v=x,e=y,w=z;

     }

     village(){}

     bool operator <(const village &V)const

     {

         return w<V.w;

     }

 };

 vector<village> V;

 int book[];

 void init()

 {

     for(int i=;i<=m;i++)

         book[i]=i;

 }

 int getx(int x)

 {

     if(book[x]!=x)

         book[x]=getx(book[x]);

     return book[x];

 }

 void mergexy(int x,int y)

 {

      book[y]=x;

 }

 int main()

 {

     while(cin>>n>>m)

     {

         V.clear();

         if(n==) break;

         init();

         int t=n;

         while(t--)

         {

             int x,y,z;

             scanf("%d%d%d",&x,&y,&z);

             village a(x,y,z);

             V.push_back(a);

         }

         sort(V.begin(),V.end());

         int number=;

         long long sum=;

         for(int i=;i<V.size();i++)

         {

             if(getx(V[i].v)!=getx(V[i].e)){

                 mergexy(getx(V[i].v),getx(V[i].e));

                 number++;

                 sum+=V[i].w;

         }

         if(number==m-)  break;

     }

     if(number==m-) cout<<sum<<endl;

     else cout<<"?"<<endl;

 }

 return ;

 }