P3623 [APIO2008] 免费道路

题目描述

新亚（New Asia）王国有 N 个村庄，由 M 条道路连接。其中一些道路是鹅卵石路，而其它道路是水泥路。保持道路免费运行需要一大笔费用，并且看上去 王国不可能保持所有道路免费。为此亟待制定一个新的道路维护计划。

国王已决定保持尽可能少的道路免费，但是两个不同的村庄之间都应该一条且仅由一条 且仅由一条免费道路的路径连接。同时，虽然水泥路更适合现代交通的需 要，但国王也认为走在鹅卵石路上是一件有趣的事情。所以，国王决定保持刚好 K 条鹅卵石路免费。

举例来说，假定新亚王国的村庄和道路如图 3(a)所示。如果国王希望保持两 条鹅卵石路免费，那么可以如图 3(b)中那样保持道路(1, 2)、(2, 3)、(3, 4)和(3, 5) 免费。该方案满足了国王的要求，因为：(1)两个村庄之间都有一条由免费道 路组成的路径；(2)免费的道路已尽可能少；(3)方案中刚好有两条鹅卵石道路 (2, 3)和(3, 4)

图 3: (a)新亚王国中村庄和道路的一个示例。实线标注的是水泥路，虚线标注 的是鹅卵石路。(b)一个保持两条鹅卵石路免费的维护方案。图中仅标出了免 费道路。

给定一个关于新亚王国村庄和道路的述以及国王决定保持免费的鹅卵石 道路数目，写一个程序确定是否存在一个道路维护计划以满足国王的要求，如果 存在则任意输出一个方案。

输入格式

输入第一行包含三个由空格隔开的整数：

N，村庄的数目(1≤N≤20,000)；

M，道路的数目(1≤M≤100,000)；

K，国王希望保持免费的鹅卵石道路数目(0≤K≤N - 1)。

此后 M 行述了新亚王国的道路，编号分别为 1 到 M。第(i+1)行述了第 i 条 道路的情况。用 3 个由空格隔开的整数述：

ui 和 vi，为第 i 条道路连接的两个村庄的编号，村庄编号为 1 到 N；

ci，表示第 i 条道路的类型。ci = 0 表示第 i 条道路是鹅卵石路，ci = 1 表 示第 i 条道路是水泥路。

输入数据保证一对村庄之间至多有一条道路连接

输出格式

如果满足国王要求的道路维护方案不存在，你的程序应该在输出第一行打印 no solution。 否则，你的程序应该输出一个符合要求的道路维护方案，也就是保持免费的 道路列表。按照输入中给定的那样输出免费的道路。如果有多种合法方案，你可 以任意输出一种。

输入输出样例

输入 #1复制

5 7 2 
1 3 0 
4 5 1 
3 2 0 
5 3 1 
4 3 0 
1 2 1 
4 2 1

输出 #1复制

3 2 0 
4 3 0 
5 3 1 
1 2 1 

解析：

首先可以确定它是一个最小生成树，在看题意，要满足鹅卵石路的条数为K。我们可以反着想：

2次Kruskal

第一次：

1.想铺水泥路，在铺鹅卵石路。这样子鹅卵石路的条数就可以确定那些鹅卵石路的一定要铺的。

2.判断他们是不是联通的。有n个点，边数一定为n-1

第二次：

3.在进行必须的鹅卵石路进行铺路，在选择那些不是那么需要的进行铺路。

4.在铺水泥路。

这里的3有个坑。鹅卵石路不一定满足K条，要特判一下。

 //先判断是最小生成树
 //在把必须连的边加入 
 //而外的边加入
 //在加入水泥边
 #include<bits/stdc++.h>
 using namespace std;
 const int N=2e5+1000,M=3e5+1000;
 struct edge{
      int u,v;
 }sn[M],er[M];
 int t1 = 0,t2 = 0;
 int n,m,k,f[N]; 
 int find(int u)
 {
 	if(f[u] != u)
	{
		f[u] = find(f[u]);
		return f[u]; 	
	}else{
		return u;
	} 
 }
 
 int main()
 {
 	int ans[200010][4];
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 1;i <= m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		if(w == 1){
			sn[t1++]={u,v};
		}else{
			er[t2++]={u,v};
		}
	}
	// 第一次判断是否全部联通 
	for(int i = 0;i <= n;i++)
	{
		f[i] = i;
	}
	int number = 0;
	for(int i = 0;i <= t1;i++)
	{
		if(find(sn[i].u) != find(sn[i].v)){
			f[find(sn[i].u)] = find(sn[i].v);
			number++;
		}
	}
	int tot = 0;
	int vis[300010];
	for(int i = 0;i <= t2;i++)
	{
		if(find(er[i].u) != find(er[i].v))
		{
			tot++;
			number++;
			f[find(er[i].u)] = find(er[i].v);
			vis[i] = 1;	
		}	
	}	
	if(tot > k && number != n-1)
	{
		printf("no solution\n");
		return 0;
	}
	// 第二次 kj
	 
	for(int i = 0;i <= n;i++)
	{
		f[i] = i;
	}
	int an = 0;
	//把一定要的e加入 
	for(int i = 0;i <= t2;i++)
	{ // 必须要连的边 
		if(vis[i])
		{
			if(find(er[i].u) != find(er[i].v))
			{
				ans[++an][0] = er[i].u;
				ans[an][1] = er[i].v;
				ans[an][2] = 0;
				f[find(er[i].u)] = find(er[i].v); 	
			} 
		}
	}
	
	for(int i = 0;i <= t2;i++)
	{
		if(!vis[i]){
			if(an == k){
				break;
			}
			if(find(er[i].u) != find(er[i].v))
			{
				ans[++an][0] = er[i].u;
				ans[an][1] = er[i].v;
				ans[an][2] = 0;
				f[find(er[i].u)] = find(er[i].v); 	
			} 
		}
	}\
	//wa #1 是这个的问题 
	if(an != k){
		printf("no solution\n");
		return 0;
	}
	for(int i = 0;i <= t1;i++) 
	{
		if(find(sn[i].u) != find(sn[i].v))
		{
			ans[++an][0] = sn[i].u;
			ans[an][1] = sn[i].v;
			ans[an][2] = 1;
			f[find(sn[i].u)] = find(sn[i].v); 
		}
	}
	if(an != n-1){
		printf("no solution\n");
		return 0;
	}
	for(int i = 1;i <= an;i++)
	{
		printf("%d %d %d\n",ans[i][0],ans[i][1],ans[i][2]);
	}
	return 0; 	
} 

时间复杂度为O(n* logn)