【bzoj3624】Apio2008—免费道路

http://www.lydsy.com/JudgeOnline/problem.php?id=3624 (题目链接)

题意

　　给出一张无向图，其中有0类边和1类边。问能否构成正好有K条0类边的生成树，并输出方案。

Solution

　　先将所有1类边加入生成树，然后再加入0类边，那么现在加入的0类边就是必须加入的0类边，将它们打上标记。然后再将并查集初始化，继续加0类边直到数量达到K，最后加1类边。

细节

　　最后必须输出换行符。。。

代码

// bzoj3624

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=20010,maxm=100010;

struct edge {int u,v,w;}e[2][maxm],ans[maxm];

int n,m,K,M[2],fa[maxn];

int find(int x) {

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

}

int main() {

	scanf("%d%d%d",&n,&m,&K);

	for (int u,v,w,i=1;i<=m;i++) {

		scanf("%d%d%d",&u,&v,&w);

		e[w][++M[w]]=(edge){u,v,w};

	}

	int cnt=0,s=0;

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

	for (int i=1;i<=M[1];i++) {

		int r1=find(e[1][i].u),r2=find(e[1][i].v);

		if (r1!=r2) cnt++,fa[r1]=r2;

	}

	if (cnt<n-1) {

		for (int i=1;i<=M[0];i++) {

			int r1=find(e[0][i].u),r2=find(e[0][i].v);

			if (r1!=r2) ans[++s]=e[0][i],cnt++,fa[r1]=r2;

		}

		if (cnt<n-1 || s>K) {puts("no solution");return 0;}

	}

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

	for (int i=1;i<=s;i++) fa[find(ans[i].u)]=find(ans[i].v);

	for (int i=1;i<=M[0];i++) {

		if (s==K) break;

		int r1=find(e[0][i].u),r2=find(e[0][i].v);

		if (r1!=r2) ans[++s]=e[0][i],fa[r1]=r2;

	}

	if (s<K) {puts("no solution");return 0;}

	for (int i=1;i<=M[1];i++) {

		int r1=find(e[1][i].u),r2=find(e[1][i].v);

		if (r1!=r2) ans[++s]=e[1][i],fa[r1]=r2;

	}

	for (int i=1;i<=s;i++) printf("%d %d %d\n",ans[i].u,ans[i].v,ans[i].w);

	return 0;

}