【生成树+贪心】免费道路

图论, 贪心

传送门：BZOJ3624

APIO2008

思路：

  • 先以1为优先构造生成树，这样0出现在生成树中的情况就最少，如果0的个数依然大于目标个数那一定无解；
  • 把上一轮出现在生成树的边先加入，再以0为优先构造生成树，使其中0的个数恰好等于目标个数；
  • 再加入1的边直到图连通即可。

注意：

  • 不要漏判无解情况

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 300000
int n,m,p,fa[N],vis[N],out[N];
struct node{int x,y,z,ID;}a[N];
int getint(){
	char ch; int sum=0;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
	for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
	return sum;
}
int gfa(int x){return x==fa[x]?x:fa[x]=gfa(fa[x]);}
bool cmp1(node x,node y){return x.z==1 && y.z==0;}
bool cmp2(node x,node y){return x.z==0 && y.z==1;}
bool cmp3(node x,node y){return x.ID<y.ID;}
int main(){
	n=getint(); m=getint(); p=getint();
	for (int i=1;i<=m;i++){a[i].x=getint(); a[i].y=getint(); a[i].z=getint(); a[i].ID=i;}
	sort(a+1,a+m+1,cmp1);
	for (int i=1;i<=n;i++) fa[i]=i;
	int j=0;
	for (int i=1;i<=m;i++){
		int x=gfa(a[i].x),y=gfa(a[i].y);
		if (x!=y){fa[x]=y; vis[a[i].ID]=1; if (a[i].z==0) j++;}
	}
	if (j>p){puts("no solution"); return 0;}
	sort(a+1,a+m+1,cmp2);
	for (int i=1;i<=n;i++) fa[i]=i;
	j=0;
	for (int i=1;i<=m && a[i].z==0;i++)
		if (vis[a[i].ID]){int x=gfa(a[i].x),y=gfa(a[i].y); fa[x]=y; out[++j]=a[i].ID;}
	for (int i=1;i<=m && a[i].z==0 && j<p;i++)
		if (!vis[a[i].ID]){int x=gfa(a[i].x),y=gfa(a[i].y); if (x!=y){fa[x]=y; out[++j]=a[i].ID;}}
	if (j<p){puts("no solution"); return 0;}
	sort(a+1,a+m+1,cmp1);
	for (int i=1;i<=m && a[i].z==1;i++){
		int x=gfa(a[i].x),y=gfa(a[i].y);
		if (x!=y){fa[x]=y; out[++j]=a[i].ID;}
	}
	sort(a+1,a+m+1,cmp3);
	for (int i=1;i<=j;i++) printf("%d %d %d\n",a[out[i]].x,a[out[i]].y,a[out[i]].z);
	
	return 0;
}