1034 Head of a Gang (30 分)

题目

题目链接

题解

并查集。

注意坑点：帮派的人数必须大于2。

代码

#include
using namespace std;
#define PSI pair
const int N = 1e5+10;

int n, k, cnt;
int fa[N];

int gongw[N]; // 每个人对于帮派的贡献，同一个通话只用记录一个人的，因为如果两个人都修改gongw，最后累加的时候会变成两倍 
int w[N]; // 每个人的通话时间，两个人都要加，为了找帮派首领 
int num[N]; // num[i] 表示以i为代表的帮派的人数，注意，代表与首领的不同，代表是find(x)，而首领只是本题中的概念 
int head[N]; // head[i] 表示以i为代表的帮派的首领 
int teamw[N]; // teamw[i] 表示以i为代表的帮派的总权重，累加该帮派的gongw即可 

map nti; // name to int：将名字转为对应的索引 
map itn; // int to name：将索引转为对应的名字 

set  s;

vector  v;

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

void join (int x, int y) {
	int rx = find (x), ry = find (y);
	if (rx != ry) fa[rx] = ry;
}

int main()
{
	cin >> n >> k;
	
	for (int i = 0;i  aa >> bb >> c;
		
		if (!nti[aa]) nti[aa] = ++ cnt, itn[cnt] = aa;
		a = nti[aa];
		
		if (!nti[bb]) nti[bb] = ++ cnt, itn[cnt] = bb;
		b = nti[bb];
		
		join (a, b);
		gongw[a] += c;
		w[a] += c;
		w[b] += c;
	}
	
	for (int i = 1;i  2) // !!!帮派人数必须大于2，题目要求的 
			v.push_back ({itn[head[item]], num[item]});

	sort (v.begin(), v.end());
	
	cout