【CF875F】Royal Questions

题意：国王的n个王子该结婚了！现在从外国来了m位公主，第i位公主的嫁妆是wi。由于进步思想的传播，每个公主在选择配偶的事情上是有自主权的，具体地，每个公主愿意从两个王子ai和bi中选取一个托付终生。而王子们就比较倒霉了，他们只能听从父王的安排。但是国王的目的并不在于为王子找到配偶，而是为了获得更多的嫁妆。现在国王可以任意安排哪个王子和哪个公主结婚（前提是公主愿意），并且不必为每个王子和公主都找到配偶，他想知道他最多能获得的总嫁妆是多少。

题解：标题已经暴露了一切。。。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn=200010;

struct node

{

	int a,b,v;

}p[maxn];

int n,m,ans;

int f[maxn],tag[maxn];

bool cmp(const node &a,const node &b)

{

	return a.v>b.v;

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+(gc^'0'),gc=getchar();

	return ret*f;

}

int find(int x)

{

	return (f[x]==x)?x:(f[x]=find(f[x]));

}

int main()

{

	n=rd(),m=rd();

	int i,a,b;

	for(i=1;i<=m;i++)	p[i].a=rd(),p[i].b=rd(),p[i].v=rd();

	sort(p+1,p+m+1,cmp);

	for(i=1;i<=n;i++)	f[i]=i;

	for(i=1;i<=m;i++)

	{

		a=find(p[i].a),b=find(p[i].b);

		if(a!=b&&(!tag[a]||!tag[b]))	tag[b]|=tag[a],f[a]=b,ans+=p[i].v;

		else	if(a==b&&!tag[a])	tag[a]=1,ans+=p[i].v;

	}

	printf("%d",ans);

	return 0;

}

巴特西

【CF875F】Royal Questions 最小生成基环树森林

【CF875F】Royal Questions

最新文章

热门文章