最小生成树之Kruskal算法

定义：

对于无向有环图，如果任意两个顶点都联通并且是一棵树，那么我们就称之为生成树

对于代权值的图，那么权值之和最小的生成树即为最小生成树

Kruskal算法

说白了，Kruskal算法就是大贪心！

对于m条边，我们按权值从小到大进行排序，从最小的进行循环，判断一下这俩个点是否已经联通了，如果没联通，就把他们联通起来，并让ans += 权值，如果联通了，就不管了

这里判断是否联通的方法是并查集

道路建设

最小生成树的裸题

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 10000 + 50
#define endl '\n'
#define mod 13331
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！

int c, n, m, k;
int ans, cnt;//ans记录答案，cnt记录几个点联通了
int fa[MAX];
struct ran{
    int x, y, val;
}tr[MAX];

bool cmp(ran a, ran b){//排序
    return a.val < b.val;
}

int finda(int x){
    return x == fa[x] ? x : fa[x] = finda(fa[x]);
}

void emerge(int x, int y){
    fa[finda(x)] = finda(y);
}

void init(){//初始化很重要！
    mem(tr, 0);
    for(int i = 1; i <= m; ++i)fa[i] = i;
    ans = 0;cnt = 0;k = 0;
}

int main(){
    io;
    while (cin>>c>>n>>m) {
        init();
        for(int i = 1;i <= n; ++i)cin>>tr[i].x>>tr[i].y>>tr[i].val;
        sort(tr + 1, tr + 1 + n, cmp);
        for(int i = 1; i <= n; ++i){
            if(finda(tr[i].x) != finda(tr[i].y)){
                ans += tr[i].val;
                cnt++;
                emerge(tr[i].x, tr[i].y);
                if(cnt == m - 1){
                    k = 1;
                    break;
                }
            }
        }
        if(k == 1 && ans <= c)cout<<"Yes\n";
        else cout<<"No\n";
    }
    
    return 0;
}

Deletion

题意：

n个点m条边的无向图

第i条边的两个顶点为u和v，这条边的权值为w

现在需要删除掉一些边，使得图中没有环，而代价就是所有删除的边的权值之和

输出最低成本

思路：

最大生成树

删除一些价值少的边，也就是需要构成价值最大的树，也就是最大生成树

用sum记录所有边的权值，减去最大生成树的权值即可

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 500000 + 50
#define endl '\n'
#define mod 13331
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m;
ll ans, sum;
int fa[MAX];

struct ran{
    int x, y, val;
}tr[MAX];

bool cmp(ran a, ran b){
    return a.val > b.val;
}

void init(){
    for(int i = 1; i <= n; ++i)fa[i] = i;
    ans = 0;
    sum = 0;
}

int finda(int x){
    return x == fa[x] ? x : fa[x] = finda(fa[x]);
}

void emerge(int x, int y){
    fa[finda(x)] = finda(y);
}

int main(){
    io;
    cin>>n>>m;
    init();
    for(int i = 1; i <= m; ++i){
        cin>>tr[i].x >> tr[i].y >> tr[i].val;
        sum += tr[i].val;
    }
    sort(tr + 1, tr + 1 + m, cmp);
    for(int i = 1; i <= m; ++i){
        if(finda(tr[i].x) != finda(tr[i].y)){
            ans += tr[i].val;
            emerge(tr[i].x, tr[i].y);
        }
    }
    cout<<sum - ans<<endl;
    return 0;
}