CF875F Royal Questions

题目简述

$n$ 个王子 $m$ 个公主，每个公主有两个备选的王子，有 $w_i$ 的嫁妆。怎样结婚可以获得最多的嫁妆（王子和公主一对一，公主只能和被选的王子结婚，可以有剩男剩女）。$2≤n≤200000,\ 1≤m≤200000,\ 1≤w_i≤10000$

思路

将王子看作点，公主看作边，嫁妆看作边权，选了一条边就是选了一个公主，考虑怎样的选边方案是合法的：

考虑树的情况，可以选择 $k$ 条边连接 $k+1$ 个点，因为选的点是什么不重要，所以相当于是求一颗最大生成树。但是这样一来会放弃一个点（王子），所以在树中再加一条边是可行的，这时候环上的王子和公主可以结婚，把环看作根，剩下的部分每个公主就与其到达的儿子节点结婚。

在 $Kruskal$ 算法的基础上求解，只需要定义一个数组 tree[] 表示当前选定的集合是否是基环树，在枚举边的时候分类讨论：

如果边连接的两个点 $u,v$ 属不同集合，且有 tree[belong[u]] | tree[belong[v]] == true，那么两个集合一定有一个不是基环树，这条边相当于把树接在环上，可以选。之后把新树的 tree[belong[v]] 更新为 tree[belong[u]] & tree[belong[v]]。因为原来的 v 集合之后就不能再接别的基环树了。
如果 $u,v$ 同属一个集合，要想选这条边只能是把树变成基环树，此时只有 tree[belong[u]]==false 时才可以选这条边。

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
#define int long long
using namespace std;
const int MaxN = 200005;
int n, m, father[MaxN], ans;
bool tree[MaxN];
struct Edge{
	int u, v, w;
	bool operator < (const Edge &y) const{
		return w > y.w;
	}
}edge[MaxN*2];

inline int Read(){
	int num = 0, op = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') op = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		num = num * 10 + ch - '0';
		ch = getchar();
	}
	return num * op;
}

inline int Find(int x){
	return father[x] == x? x : father[x] = Find(father[x]);
}

inline void Kruskal(){
	sort(edge+1, edge+1+m);
	for(int i=1; i<=m; i++){
		int x = Find(edge[i].u), y = Find(edge[i].v);
		if(x != y && (tree[x] || tree[y])){
			father[x] = y;
			ans += edge[i].w;
			tree[y] = tree[x] & tree[y];
		}
		else if(x == y && tree[x]){
			tree[x] = false;
			ans += edge[i].w;
		}
	}
	return;
}

signed main(){
	n = Read(), m = Read();
	for(int i=1; i<=n; i++){
		father[i] = i;
		tree[i] = true;
	}
	for(int i=1; i<=m; i++)
		edge[i].u = Read(), edge[i].v = Read(), edge[i].w = Read();
	Kruskal();
	printf("%lld", ans);
	return 0;
}