Rainy2k
0%

最小生成树

Posted on Edited on In

模板

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 6000 + 5;
int fa[maxn],sz[maxn];
struct node{
    int x, y, w;
} e[maxn];
bool operator < (node a,node b) {
    return a.w < b.w;
}
int find(int x) {
    return (x == fa[x] ? x : find(fa[x]));
}
void init(int n) {
    for (int i = 1; i <= n;i++) {
        fa[i] = i;
        sz[i] = 1;
    }
}
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        int n;
        scanf("%d", &n);
        init(n);
        for (int i = 1; i <= n-1;i++) {
            scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].w);
        }
        sort(e + 1, e + 1 + n - 1);
        ll ans = 0;
        for (int i = 1; i <= n - 1;i++) {
            int x = find(e[i].x);
            int y = find(e[i].y);
            int w = e[i].w;
            if(x==y)
                continue;
            ans += (w + 1) * (sz[x] * sz[y] - 1);
            fa[x] = y;
            sz[y] += sz[x];
        }
            printf("%lld\n", ans);
    }
}

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
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxe = 2e5 + 100;
struct edge{
    int v,w,next;
}e[maxe<<1];
int head[5020],dis[5020],n,m,now,cnt,ans;
bool vis[5020];
void add(int u,int v,int w){
    cnt++;
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void init(){
    scanf("%d%d", &n, &m);
    int u, v, w;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d", &u, &v, &w);
        add(u,v,w),add(v,u,w);
    }
}
int prim(int a){
    memset(dis,inf,sizeof(dis));
    dis[a] = 0;
    now = a;
    for (int i = head[a]; i; i = e[i].next)
        dis[e[i].v] = min(dis[e[i].v], e[i].w);
    for (int cnt = 1; cnt <= n - 1;cnt++){
        int minn = inf;
        vis[now] = true;
        for (int i = 1; i <= n;i++){
            if (!vis[i] && minn > dis[i]){
            minn = dis[i];
            now = i;
            }
        }
        ans += minn;
        for (int i = head[now]; i; i = e[i].next){
            if (!vis[e[i].v])
                dis[e[i].v] = min(dis[e[i].v], e[i].w);
        }
    }
    return ans;
}
int main(){
    init();
    printf("%d",prim(1));
    system("pause");
    return 0;
}

Kruskal

贪心策略：n个节点的最小生成树里面包含了n-1条边，这n-1条边是不可以成环的，这样就可以保证联通了，所以我们只要把这n-1条边选出来，因为是最小生成树，所以我们要找最小的权边

所以基本的思路就定了：

  • 存边
  • 按照权值将这些边排序
  • 排序完了开始遍历，决定把谁加入MST
  • 判断的条件是：是否成环，成环的话就不要，不成环的话就加入MST
  • 接下来要解决的问题就是怎么判断成环->利用并查集，共祖->成环
  • 共祖在某种意义上就等于联通
  • 所以有一个查的过程和并的过程
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5020;
const int F = 2e5 + 100;
struct node{
    int u, v, c;
} e[F];
int f[N],cnt,sum;
int find(int x){
    return f[x] == x ? x : f[x] = find(f[x]);}
bool unionset(int a,int b){
    a = find(a),b = find(b);
    if(a!=b){
        f[b] = a;
        return true;
    }
    return false;
}
bool cmp(node a,node b){
    return a.c < b.c;
}
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <=m;i++){
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].c);
    }
    sort(e + 1, e + 1 + m, cmp);
    for (int i = 1; i <= n;i++)
        f[i] = i;
    for (int i = 1; i <= m;i++){
        if(unionset(e[i].u,e[i].v)){
            cnt++;
            sum += e[i].c;
        }
        if(cnt==n-1)
            break;
    }
    printf("%d",sum);
    //system("pause");
    return 0;
}

例题

走廊泼水节

https://ac.nowcoder.com/acm/contest/1056/A
题意

将一棵树加不同权值的边,变成一个完全图,问加的权值和最小为多少?
思路
推论:对于两棵树,要在两棵树之间选择一条边,仍然是最小生成树,必然是选择两棵树之间权值最小的边
考虑Kruskal的建树方式
本题从也从最短的边开始计算
代码 : https://xlorpaste.cn/tjw8rk