Networking

poj1287:http://poj.org/problem?id=1287

题意：平面上有许多点，又有许多边。每条边有一定的长度，且只会连接两个不同的点。现需要从这些边中选择某些边，使得尽可能多的点直接或间接相连。同时，又要选取的边的总长度最小。

题解：本题就是去除重边，然后kruska运用。去重时候，我采用一个二维数组选取最小的边放进数组，然后遍历数组，如果有边则struct存入要处理的边。但是，看了别人的看法;程中可无视重边，因为排序之后，每次总是把最小的边加入,而且没两个点只能加一次，所以可以无视。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int MAXN=;

 const int MAXM=;

 int pa[MAXN],cnt;

 int g[][]; //记录最短边

 struct Node{

     int u;

     int v;

     int w;

     bool operator<(const Node &a)const{

         return w<a.w;

     }

 }edge[MAXM];

 int n,m;

 void UFset(){//初始化

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

      pa[i]=-;

 }

 int Find(int x){

     int s;

     for(s=x;pa[s]>=;s=pa[s]);

     while(s!=x){

         int temp=pa[x];

         pa[x]=s;

         x=temp;

     }

     return s;

 }

 void Union(int R1,int R2){

      int r1=Find(R1);

      int r2=Find(R2);

      int temp=pa[r1]+pa[r2];

      if(pa[r1]>pa[r2]){

          pa[r1]=r2;

          pa[r2]=temp;

      }

      else{

          pa[r2]=r1;

          pa[r1]=temp;

      }

 }

 void kruskal(){

     int sum=;

     int u,v;

     int num=;

     UFset();

     for(int i=;i<cnt;i++){

         u=edge[i].u;v=edge[i].v;

         if(Find(u)!=Find(v)){

             sum+=edge[i].w;

             Union(u,v);

             num++;

         }

     if(num>=n-)break;

     }

     printf("%d\n",sum);

 }

 int main(){

     int a,b,w;

     while(~scanf("%d",&n)&&n){

         scanf("%d",&m);

         cnt=;

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

            for(int j=;j<=n;j++)

             g[i][j]=;

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

           scanf("%d%d%d",&a,&b,&w);

           if(g[a][b]>w){//去重

               g[a][b]=g[b][a]=w;

           }

         }

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

           for(int j=;j<=n;j++){

               if(g[i][j]!=){//转化边

                       edge[cnt].u=i;

                      edge[cnt].v=j;

                     edge[cnt++].w=g[i][j];

                     g[i][j]=g[j][i]=;

               }

           }

          sort(edge+,edge+cnt);//排序

          kruskal();

     }

 }