OI

【模板】最小生成树

prim算法

プリーム法　　

主要要考虑一下如何O(n^2)解决

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
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int MAX=5005,INF=2147483647;

int n,m;
int g[MAX][MAX];

int dist[MAX],mst=0,mind,t;
int prim(){
    bool vis[MAX]={0};
    int i,j;
    dist[1]=0;
    vis[1]=1;
    for(i=2;i<=n;i++)
        dist[i]=g[1][i];
    
    for(i=2;i<=n;i++){
        mind=INF;
        for(j=1;j<=n;j++)
            if(!vis[j]&&dist[j]<mind){
                mind=dist[j];
                t=j;
            }
        mst+=mind;
        for(j=1;j<=n;j++)
            if(!vis[j]&&dist[j]>g[t][j])
                dist[j]=g[t][j];
        vis[t]=1;
    }
    return mst;
}

int main(){
    scanf("%d%d",&n,&m);
    int i,j,x,y,z;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            g[i][j]=INF;
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        if(g[x][y]>z){
            g[x][y]=z;
            g[y][x]=z;
        }
    }

    printf("%d",prim());
    return 0;
}

kruskal算法

クルスカル法　　

要用到快排、并查集，STL调一下很方便。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=5005,MAXM=200005;
struct edge{
    int st,ed,val;
};
edge g[MAXM];

int n,m;

bool cmp(edge &a,edge &b){
    return a.val<b.val;
}

int a[MAXN];

int find(int x){
    if(x!=a[x])a[x]=find(a[x]);
    return a[x];
}

inline void unite(int x,int y){
    a[find(x)]=find(y);
}

int kruskal(edge g[]){
    sort(g,g+m,cmp);
    for(int i=1;i<=n;i++)
        a[i]=i;
    
    int k=0,mst=0;
    for(int i=0;i<m;i++)
        if(find(g[i].st)!=find(g[i].ed)){
            unite(g[i].st,g[i].ed);
            mst+=g[i].val;
            k++;
            if(k==n-1)break;
        }
    if(k<n-1)return -1;
    else return mst;
}

int main(){
    int x,y,z;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
        scanf("%d%d%d",&g[i].st,&g[i].ed,&g[i].val);
    int ans=kruskal(g);
    if(ans==-1)printf("orz");
    else printf("%d",ans);
    
    return 0;
}