bzoj 3624: [Apio2008]免费道路【生成树+贪心】

先把水泥路建生成树，然后加鹅卵石路，这里加的鹅卵石路是一定要用的（连接各个联通块），然后初始化并查集，先把必需的鹅卵石路加进去，然后随便加鹅卵石路直到k条，然后加水泥路即可。

注意判断无解

#include<iostream>

#include<cstdio>

using namespace std;

const int N=20005,M=100005;

int n,m,k,f[N],ta,tb,con;

bool v[M];

struct qwe

{

	int u,v;

	qwe(int U=0,int V=0)

	{

		u=U,v=V;

	}

}a[M],b[M],ans[N];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

int zhao(int x)

{

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

}

int main()

{

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

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

	{

		int x=read(),y=read(),z=read();

		if(z)

			a[++ta]=qwe(x,y);

		else

			b[++tb]=qwe(x,y);

	}

	if(tb<k)

	{

		printf("no solution\n");

		return 0;

	}

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

		f[i]=i;

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

	{

		int fu=zhao(a[i].u),fv=zhao(a[i].v);

		if(fu!=fv)

			f[fu]=fv;

	}

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

	{

		int fu=zhao(b[i].u),fv=zhao(b[i].v);

		if(fu!=fv)

			f[fu]=fv,v[i]=1,k--;

	}

	if(k<0)

	{

		printf("no solution\n");

		return 0;

	}

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

		f[i]=i;

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

		if(v[i])

		{

			f[zhao(b[i].u)]=zhao(b[i].v);

			ans[++con]=qwe(b[i].u,b[i].v);

		}

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

	{

		int fu=zhao(b[i].u),fv=zhao(b[i].v);

		if(fu!=fv)

		{

			f[fu]=fv,k--;

			ans[++con]=qwe(b[i].u,b[i].v);

		}

	}

	if(k)

	{

		printf("no solution\n");

		return 0;

	}

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

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

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

	{

		int fu=zhao(a[i].u),fv=zhao(a[i].v);

		if(fu!=fv)

		{

			f[fu]=fv;

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

		}

	}

	return 0;

}

巴特西

bzoj 3624: [Apio2008]免费道路【生成树+贪心】

最新文章

热门文章