poj 1259 Agri-Net（最小生成树）

题意：模板题和2485差不多就是求相连后的最小值。
 1 #include <iostream>
 2  #include<cstdio>
 3  #include<cstring>
 4  #include<cstdlib>
 5  #include<stack>
 6  #include<queue>
 7  #include<cmath>
 8  #include<algorithm>
 9  using namespace std;
10  int bin[110];
11  struct node
12  {
13      int u,v,w;
14  } q[30000];
15  bool cmp(node x,node y)
16  {
17      return x.w<y.w;
18  }
19  int find(int a)
20  {
21      if(a==bin[a])
22          return a;
23      else
24          bin[a]=find(bin[a]);
25  }
26  int main()
27  {
28      int i,j,n,num,p,m;
29      int x,y;
30      int sum;
31      while(~scanf("%d",&n))
32      {
33          num=0; m=n*n; sum=0;
34          for(i=1; i<=n; i++)
35              bin[i]=i;
36          p=0;
37          for(i=1; i<=n; i++)
38              for(j=1; j<=n; j++)
39              {
40                  q[p].u=i;  q[p].v=j;
41                  scanf("%d",&q[p].w);
42                  p++;
43              }
44          sort(q,q+m,cmp);
45          for(i=0; i<m; i++)
46          {
47              x=find(q[i].u);
48              y=find(q[i].v);
49              if(x!=y)
50              {
51                  sum+=q[i].w;
52                  num++;
53                  bin[x]=y;
54              }
55              if(num==n-1)
56              {
57                  break;
58              }
59          }
60          cout<<sum<<endl;
61      }
62  }