Networking

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

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

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=1000;
 7 const int MAXM=10000;
 8 int pa[MAXN],cnt;
 9 int g[100][100]; //记录最短边 
10 struct Node{
11     int u;
12     int v;
13     int w;
14     bool operator<(const Node &a)const{
15         return w<a.w;
16     }
17 }edge[MAXM];
18 int n,m;
19 void UFset(){//初始化 
20     for(int i=1;i<=n;i++)
21      pa[i]=-1;
22 }
23 int Find(int x){
24     int s;
25     for(s=x;pa[s]>=0;s=pa[s]);
26     while(s!=x){
27         int temp=pa[x];
28         pa[x]=s;
29         x=temp;
30     }
31     return s;
32 }
33 void Union(int R1,int R2){
34      int r1=Find(R1);
35      int r2=Find(R2);
36      int temp=pa[r1]+pa[r2];
37      if(pa[r1]>pa[r2]){
38          pa[r1]=r2;
39          pa[r2]=temp;
40      }
41      else{
42          pa[r2]=r1;
43          pa[r1]=temp;
44      }
45     
46 }
47 void kruskal(){
48     int sum=0;
49     int u,v;
50     int num=0;
51     UFset();
52     for(int i=1;i<cnt;i++){
53         u=edge[i].u;v=edge[i].v;
54         if(Find(u)!=Find(v)){
55             sum+=edge[i].w;
56             Union(u,v);
57             num++;
58         }
59     if(num>=n-1)break;    
60         
61     }
62     printf("%d
",sum);
63     
64 }
65 int main(){
66     int a,b,w;
67     while(~scanf("%d",&n)&&n){
68         scanf("%d",&m);
69         cnt=1;
70          for(int i=1;i<=n;i++)
71            for(int j=1;j<=n;j++)
72             g[i][j]=100000;
73         for(int i=1;i<=m;i++){
74           scanf("%d%d%d",&a,&b,&w);
75           if(g[a][b]>w){//去重 
76               g[a][b]=g[b][a]=w;
77           
78           }
79         }
80         for(int i=1;i<=n;i++)
81           for(int j=1;j<=n;j++){
82               if(g[i][j]!=100000){//转化边 
83                       edge[cnt].u=i;
84                      edge[cnt].v=j;
85                     edge[cnt++].w=g[i][j];
86                     g[i][j]=g[j][i]=100000;
87               }
88           }
89         
90          sort(edge+1,edge+cnt);//排序 
91          kruskal();
92     }
93 }

View Code