51nod1212无向图最小生成树

发表于 | 分类于 |

1212 无向图最小生成树
基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题
收藏
关注
N个点M条边的无向连通图，每条边有一个权值，求该图的最小生成树。

Input
第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000)
第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000)
Output
输出最小生成树的所有边的权值之和。
Input示例
9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8
Output示例
37
prim算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<stdio.h>
#include<string.h>
#define inf 0x3f3f3f3f
int G[1001][1001];
int vis[1001],lowc[1001];
int prim(int G[][1001],int n){
    int i,j,p,minc,res=0;
    memset(vis,0,sizeof(vis));//全部初值为0表示没有访问过；
    vis[1]=1;
    for(i=2;i<=n;i++)
        lowc[i]=G[1][i];
    for(i=2;i<=n;i++){
        minc=inf;
        p=-1;
        for(j=1;j<=n;j++){
            if(vis[j]==0&&lowc[j]<minc)
                {minc=lowc[j];p=j;}
        }
        if(inf==minc) return -1;//原图不连通
        res+=minc;
        vis[p]=1;
        for(j=1;j<=n;j++){//更新lowc[]
            if(vis[j]==0&&lowc[j]>G[p][j])
                lowc[j]=G[p][j];
        }
    }
    return res;
}
int main(){
    int n,m;
    int x,y,w;
    while(~scanf("%d %d",&n,&m)){
        memset(G,inf,sizeof(G));
        while(m--){
            scanf("%d%d%d",&x,&y,&w);
            G[x][y]=G[y][x]=w;
        }
        printf("%d\n",prim(G,n));
    }
}

kruskal算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <stdio.h>
#include <algorithm>

using namespace std;

#define _min_(a,b) ((a)<(b)?(a):(b))
#define INF 0x3f3f3f3f
#define MAX_N 1005
#define MAX_E 50005

struct edge
{
    int u;
    int v;
    int cost;
};

edge es[MAX_E];

int N,M;
int W[MAX_N][MAX_N];
int mincost[MAX_N];
bool used[MAX_N];

bool cmp(edge e1, edge e2)
{
    return e1.cost < e2.cost;
}

// union-find set
int par[MAX_N];
int rank[MAX_N];
void init_inion_find(int n)
{
    for(int i=0;i<n;i++){
        par[i]=i;
        rank[i]=0;
    }
}
int find(int x)
{
    if(par[x]==x){
        return x;
    }else{
        return par[x]=find(par[x]);
    }
}
void unite(int x,int y)
{
     x=find(x);
     y=find(y);
     if(x==y){
         return;
     }
     if(rank[x]<rank[y]){
         par[x]=y;
     }else{
          par[y]=x;
          if(rank[x]==rank[y]){
              rank[x]++;
          }
     }
}
bool same(int x, int y)
{
     return find(x)==find(y);
}
// end of union-find set

void init()
{
    for(int i=0;i<MAX_N;i++){
        for(int j=0;j<MAX_N;j++){
            W[i][j]=INF;
        }
        mincost[i]=INF;
        used[i]=false;
    }
}

long long kruskal()
{
    long long res=0;
    for(int i=0;i<M;i++){
        edge e=es[i];
        if(!same(e.u, e.v)){
            unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}

int main()
{
    //freopen("18_kruskal.txt","r",stdin);
    init();
    scanf("%d %d",&N,&M);
    for(int i=0;i<M;i++){
        int u,v,cost;
        scanf("%d %d %d",&u,&v,&cost);
        es[i].u = u-1;
        es[i].v = v-1;
        es[i].cost = cost;
    }
    sort(es,es+M,cmp);

    init_inion_find(N);

    long long res = kruskal();
    printf("%lld\n",res);
    return 0;
}