Networking---poj1287最小生成树

最小生成树模板题类似的还有：poj1258 hdu1233代码几乎一样；

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<math.h>
 6 #include<map>
 7 #define N 110
 8 #define INF 0xfffffff
 9 using namespace std;
10 
11 int ans, n, m, dist[N], maps[N][N], vis[N];//dist[i]代表当前起点到i的最小距离；
12 
13 void Init()
14 {
15     for(int i=0; i<=n; i++)
16     {
17         dist[i] = INF;
18         vis[i] = 0;
19         for(int j=0; j<=n; j++)
20         if(i==j)
21             maps[i][j] = 0;
22         else
23             maps[i][j] = INF;
24     }
25 }
26 
27 void Prim(int start)
28 {
29     for(int i=1; i<=n; i++)
30         dist[i] = maps[start][i];
31     vis[start] = 1;
32     for(int i=1; i<=n; i++)
33     {
34         int Min = INF, index=-1;
35 
36         for(int j=1; j<=n; j++)
37         {
38             if(vis[j]==0 && Min>dist[j])
39             {
40                 Min = dist[j];
41                 index = j;
42             }
43         }
44         if(index == -1)break;
45         vis[index] = 1;
46         ans += Min;
47         for(int j=1; j<=n; j++)
48         {
49             if(vis[j]==0 && maps[index][j] < dist[j])
50             {
51                 dist[j] = maps[index][j];
52             }
53         }
54     }
55 }
56 
57 int main()
58 {
59     int a, b, c;
60     while(scanf("%d", &n),n)
61     {
62         ans=0;
63         Init();
64         scanf("%d", &m);
65         for(int i=0; i<m; i++)
66         {
67             scanf("%d%d%d", &a, &b, &c);
68             maps[a][b] = maps[b][a] = min(maps[a][b], c);
69         }
70         Prim(1);
71         printf("%d
", ans);
72     }
73     return 0;
74 }

prim

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<map>
#define N 110
#define INF 0xfffffff
using namespace std;

int n, f[N], m;

struct node
{
    int x, y, d;
}a[N*N];

int cmp(node p, node q)
{
    return p.d < q.d;
}

int Find(int x)
{
    if(x != f[x])
        f[x] = Find(f[x]);
    return f[x];
}

int main()
{
    int ans, px, py;
    while(scanf("%d", &n),n)
    {
        ans=0;
        for(int i=0; i<=n; i++)
            f[i] = i;
        scanf("%d", &m);
        for(int i=0; i<m; i++)
        {
            scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].d);
        }
        sort(a, a+m, cmp);
        for(int i=0; i<m; i++)
        {
            px = Find(a[i].x);
            py = Find(a[i].y);
            if(px != py)
            {
                f[px] = py;
                ans+=a[i].d;
            }
        }
        printf("%d
", ans);
    }
    return 0;
}

Kruskal