BZOJ3624: [Apio2008]免费道路 Kruskal+构造

题解：

呵，不要欺骗我的感情好么？

明明半年之前我还会做这道题呢。。。

算了闲话少说，进入正题。

题目中的边分为两种，我们要构造出一颗生成树使得两种边的个数均符合要求。

考虑优先加入a类边以及优先加入b类边，这样就能得出合法生成树中a类边个数的上界和下界。

事实上，上下界区间中的任何一个值都是能够取到的。

我们考虑这样构造合法的生成树：考虑优先加入b类边，这样就能得到一些必须加入的a类边。

将加入的所有b类边删除，加入一些刚才没有加入的a类边（在此过程中不能产生环）直到a类边个数恰好等于要求。

再加入所有b类边直到形成一颗完整的生成树。

只要边数在区间中则一定能够构造出来。

就按照这种方法构造就行了。

代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

#define N 20010
#define M 100010
int n,m,k;

struct Edge{
	int a,b;
	Edge(){}
	Edge(int _a,int _b):a(_a),b(_b){}
};
vector<Edge>A,B,C;

int r[N],siz[N];
inline int find(int x){
	return x==r[x]?x:r[x]=find(r[x]);
}
inline void merge(int ra,int rb){
	if(siz[ra]>siz[rb])
		swap(ra,rb);
	siz[rb]+=siz[ra];
	r[ra]=rb;
}

int a[M],b[M],c[M];

inline int getc(){
	static const int L=1<<15;
	static char buf[L],*S=buf,*T=buf;
	if(S==T){
		T=(S=buf)+fread(buf,1,L,stdin);
		if(S==T)
			return EOF;
	}
	return*S++;
}
inline int getint(){
	int c;
	while(!isdigit(c=getc()));
	int x=c-'0';
	while(isdigit(c=getc()))
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}

inline int solve(vector<Edge>&s){
	int i,j,ra,rb,ans=0;
	for(i=1;i<=n;++i)
		r[i]=i,siz[i]=1;
	for(i=0;i<s.size();++i){
		ra=find(s[i].a);
		rb=find(s[i].b);
		if(ra!=rb){
			++ans;
			merge(ra,rb);
		}
	}
	return ans;
}

bool ok[M];

int main(){
#ifndef ONLINE_JUDGE
	freopen("tt.in","r",stdin);
#endif
	n=getint(),m=getint(),k=getint();
	int i,j;
	for(i=1;i<=m;++i){
		a[i]=getint();
		b[i]=getint();
		c[i]=getint();
		C.push_back(Edge(a[i],b[i]));
		if(c[i]==0)
			A.push_back(Edge(a[i],b[i]));
		else
			B.push_back(Edge(a[i],b[i]));
	}
	int ansa=solve(A);
	int ansc=solve(C);
	int ansb=solve(B);
	if(ansc!=n-1||k<n-1-ansb||k>ansa)
		puts("no solution");
	else{
		int ra,rb,edge=0;
		for(i=1;i<=m;++i){
			if(c[i]==0){
				ra=find(a[i]),rb=find(b[i]);
				if(ra!=rb){
					ok[i]=1;
					++edge;
					merge(ra,rb);
				}
			}
		}
		for(i=1;i<=n;++i)
			r[i]=i,siz[i]=1;
		for(i=1;i<=m;++i)
			if(ok[i]){
				ra=find(a[i]),rb=find(b[i]);
				if(ra!=rb)
					merge(ra,rb);
			}
		for(i=1;i<=m;++i)
			if(c[i]==0&&!ok[i]){
				ra=find(a[i]),rb=find(b[i]);
				if(ra!=rb&&edge<k){
					ok[i]=1;
					++edge;
					merge(ra,rb);
				}
			}
		for(i=1;i<=m;++i)
			if(c[i]){
				ra=find(a[i]),rb=find(b[i]);
				if(ra!=rb){
					ok[i]=1;
					merge(ra,rb);
				}
			}
		for(i=1;i<=m;++i)
			if(ok[i])
				printf("%d %d %d\n",a[i],b[i],c[i]);
	}
	return 0;
}