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 \le N \le 2 \times 10^4)$；

$M$，道路的数目 $(1 \le M \le 10^5)$；

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

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

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

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

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

输出格式

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

输入输出样例 #1

输入 #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

说明/提示

数据范围

对于 $100\%$ 的数据。保证 $1 \le N \le 2 \times 10^4$，$1 \le M \le 10^5$，$0 \le K \le N-1$。 代码：

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int fa[20010];
//先跑水泥路（1）
struct node {
	int x, y;
	bool rd;
};
bool cmp(node a, node b) {
	return a.rd > b.rd;
}
bool pmc(node a, node b) {
	return a.rd < b.rd;
}
int find(int x) {
	if (fa[x] == x) {
		return x;
	}
	return fa[x] = find(fa[x]);
}
void add(int x, int y) {
	x = find(x), y = find(y);
	if (x != y) {
		fa[x] = y;
	}
}
vector<node> edges;
vector<node> ans;
int main() {
	cin >> n >> m >> k;
	int cnt = 0;
	//输入
	for (int i = 1; i <= m; i++) {
		int u, v;
		bool c;
		cin >> u >> v >> c;
		if (!c) {
			cnt++;
		}
		edges.push_back({u, v, c});
	}
	if (cnt < k) {
		cout << "no solution";
		return 0;
	}
	//跑水泥路
	for (int i = 1; i <= n; i++) {
		fa[i] = i;
	}
	sort(edges.begin(), edges.end(), cmp);
	int i = 0;
	for (i = 0; i < edges.size(); i++) {
		if (!edges[i].rd) {
			break;
		}
		if (find(edges[i].x) != find(edges[i].y)) {
			add(edges[i].x, edges[i].y);
		}
	}
	cnt = 0;
	for (; i < edges.size(); i++) {
		if (find(edges[i].x) != find(edges[i].y)) {
			add(edges[i].x, edges[i].y);
			cnt++;
			ans.push_back({ edges[i].x, edges[i].y, edges[i].rd });
			edges.erase(edges.begin() + i);
			i--;
		}
	}
	if (cnt > k) {
		cout << "no solution";
		return 0;
	}
	//查联通
	for (i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (find(i) != find(j)) {
				cout << "no solution";
				return 0;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		fa[i] = i;
	}
	for (auto x : ans) {
		add(x.x, x.y);
	}
	//加其他鹅卵石路
	sort(edges.begin(), edges.end(), pmc);
	while (cnt < k) {
		if (find(edges[0].x) != find(edges[0].y)) {
			add(edges[0].x, edges[0].y);
			cnt++;
			ans.push_back({ edges[0].x, edges[0].y, edges[0].rd });
		}
	}
	for (i = 0; i < edges.size(); i++) {
		if (edges[i].rd) {
			break;
		}
	}
	//加水泥路
	for (; i < edges.size(); i++) {
		if (find(edges[i].x) != find(edges[i].y)) {
			add(edges[i].x, edges[i].y);
			cnt++;
			ans.push_back({ edges[i].x, edges[i].y, edges[i].rd });
		}
	}
	if (cnt != k) {
		cout << "no solution";
		return 0;
	}
	//输出
	cout << cnt << endl;
	for (auto x : ans) {
		cout << x.x << " " << x.y << " " << x.rd << endl;
	}
	return 0;
}