最小生成树

我们来总结一下，prim算法和克鲁斯卡尔算法都可以判断是否是一棵树，但是克鲁斯卡尔算法可以用于多个联通分量的求最小生成森林，且不改变原来的联通分量

看一个这个题目，是一个最小生成树的题目，但是有细节需要处理，第一是我们需要增加一个新的节点，和全部的节点连接，权重为 a ，且我们优惠价格可能会高于 a，这也是我们需要注意的

#include<bits/stdc++.h>
using namespace std;

#define inf 0xffffff
#define int long long
int n,m;
int ans,cnt;
const int N = (int)1e5+5;
struct dian{
    int to,w;
};
vector<dian> e[N];
int vis[N];
int d[N]; // 记录和圈外的距离 
priority_queue<pair<int,int>> q;

void add(int a,int b,int w){
    e[a].push_back({b,w});
    //e[b].push_back({a,w});
}

int prim(int s){
    q.push({0,s});
    for(int i=1;i<=m;i++) d[i] = inf;
    d[s] = 0;  // 这个不能漏了 
    while(q.size()){
        int dis = -q.top().first, node = q.top().second;
        q.pop(); 
        if(vis[node]) continue;
        vis[node] = 1;
//        if(d[node]>n) ans += n;
//        else ans += d[node]; 
		ans += d[node]; 
        cnt++;
        for(auto edge:e[node]){
            int to = edge.to , w = edge.w;
            if(d[to]>w){
                d[to] = w>n?n:w;
                q.push({-d[to],to});
            }
        }
    }
    return cnt == m;
}


signed main(){
    cin >> n >> m; // n是价钱，m是数量 
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            int a;
            cin >> a;
            if(a==0) continue;
            add(i,j,a);
        }
    }
    // 新增加一个 点，和其他点的距离是 n
    for(int i=1;i<=m;i++){
        add(i,m+1,n);
        add(m+1,i,n);
    } 
    prim(m+1);
    cout << ans   ;
    return 0;
}

我们再来学一个克鲁斯卡尔算法

我们看一下这个题目，我们需要懂一个事情，如果选 n - k 条边，就会产生 k 个联通分量，且我们还可以通过并查集fa[i] 是否等于 i 来判断联通分量的个数

#include<bits/stdc++.h>
using namespace std;

const int N = 1e4+5;
struct node{
	int u,v,w;
	bool operator<(node b){
		return w < b.w;
	}
}e[N];
int n,m,k;
int fa[N];
int find(int x){
	if(x==fa[x]) return x;
	return fa[x] = find(fa[x]);
}
int ans = 0;
int cnt = 0;

bool kruskal(){
	sort(e+1,e+1+m);
	for(int i=1;i<=n;i++){
		fa[i] = i;
	}	
	for(int i=1;i<=m;i++){
		int u = e[i].u , v = e[i].v , w = e[i].w;
		int x = find(u), y = find(v);
		if(x!=y){
			fa[x] = y;
			cnt++; // 边数加一
			ans += w; 
			if(cnt==n-k) break;
		}
	}
	return 0; // 这里无所谓 
}

int main(){
	cin >> n >> m >> k;
	int x,y,l;
	for(int i=1;i<=m;i++){
		cin >> e[i].u >> e[i].v >> e[i].w;
	}
	kruskal();
	int num = 0;
	for(int i=1;i<=n;i++){
		if(fa[i]==i) num++;
	}
	if(num>k) cout << "No Answer";
	else cout << ans;
	return 0;
}