BZOJ3624：[APIO2008]免费道路

浅谈并查集：https://www.cnblogs.com/AKMer/p/10360090.html

题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=3624

题目要求的就是恰好包含\(k\)条鹅卵石路的生成树。

首先我们用水泥边建出生成树森林，然后再用鹅卵石边把森林连成一棵树。

如果需要用到的鹅卵石边大于\(k\)则无解。

如果无法连成一棵树则无解。

连成一棵树之后也许此时用到的鹅卵石边比\(k\)要小，我们暂且称已经用到的鹅卵石边为必要边。

我们把树全部拆掉，然后把必要边连上，在看看能不能把不足的\(k\)条鹅卵石边补上，补得上就有解，否则无解。

剩下的用水泥边填上即可。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n+m)\)

代码如下：

#include <cstdio>

using namespace std;

const int maxn=2e4+5,maxm=1e5+5;

int fa[maxn];bool bo[maxm];

int n,m,k,cnt1,cnt2,cnt,tot;

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

struct road {

	int a,b;

	road() {}

	road(int _a,int _b) {

		a=_a,b=_b;

	}

}cob[maxm],cem[maxm],ans[maxn];

int find(int x) {

	if(fa[x]==x)return x;

	return fa[x]=find(fa[x]);

}

int main() {

	tot=n=read(),m=read(),k=read();

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

		int a=read(),b=read(),opt=read();

		if(opt)cem[++cnt1]=road(a,b);

		else cob[++cnt2]=road(a,b);

	}

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

	for(int i=1;i<=cnt1;i++) {

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

		if(p==q)continue;

		fa[p]=q,tot--;

	}

	if(tot-1>k) {puts("no solution");return 0;}

	for(int i=1;i<=cnt2;i++) {

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

		if(p==q)continue;

		fa[p]=q,tot--,bo[i]=1;

	}

	if(tot!=1) {puts("no solution");return 0;}

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

	for(int i=1;i<=cnt2;i++)

		if(bo[i]) {

			ans[++cnt]=cob[i];

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

			fa[p]=q;k--;

		}

	for(int i=1;i<=cnt2&&k;i++)

		if(!bo[i]) {

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

			if(p==q)continue;

			fa[p]=q,k--;ans[++cnt]=cob[i];

		}

	if(k) {puts("no solution");return 0;}

	for(int i=1;i<=cnt;i++)

		printf("%d %d 0\n",ans[i].a,ans[i].b);

	for(int i=1;i<=cnt1;i++) {

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

		if(p==q)continue;

		printf("%d %d 1\n",cem[i].a,cem[i].b);

		fa[p]=q;

	}

	return 0;

}

巴特西

BZOJ3624：[APIO2008]免费道路

最新文章

热门文章