免费道路（1s 128MB）roads
【输入样例】
5 7 2
1 3 0
4 5 1
3 2 0
5 3 1
4 3 0
1 2 1
4 2 1
【输出样例】
3 2 0
4 3 0
5 3 1
1 2 1
题解：
主要算法：生成树；
题意即为求一棵刚好拥有k条鹅卵石路的生成树
那么我们先将所有水泥路加入图中
就可以知道必须要加入的鹅卵石路
将这些边加入新树中
接下来再随意地按树的结构加入至k条鹅卵石路
并再更加随意按树结构加水泥路至连通
那么就得到了合法方案
判断过程中无解的情况：
1.所有边加入都无法连通
2.鹅卵石路不足k条
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int me = 1000233;
struct shape
{
int x, y, z;
};
shape a[me], ans[me];
int tot, num, cnt;
int n, m, k;
int fat[me];
inline int Get()
{
int x = 0;
char c = getchar();
while(‘0‘ > c || c > ‘9‘) c = getchar();
while(‘0‘ <= c && c <= ‘9‘)
{
x = (x << 3) + (x << 1) + c - ‘0‘;
c = getchar();
}
return x;
}
int Find(int x)
{
return (fat[x] != x) ? fat[x] = Find(fat[x]) : x;
}
int main()
{
n = Get(), m = Get(), k = Get();
for(int i = 1; i <= n; ++i) fat[i] = i;
for(int i = 1; i <= m; ++i)
{
a[i].x = Get(), a[i].y = Get(), a[i].z = Get();
if(a[i].z)
{
int u = Find(a[i].x);
int v = Find(a[i].y);
if(u != v) fat[u] = v, ++cnt;
}
}
for(int i = 1; i <= m; ++i)
if(!a[i].z)
{
int u = Find(a[i].x);
int v = Find(a[i].y);
if(u != v)
{
fat[u] = v;
ans[++tot] = a[i];
}
}
if(cnt + tot != n - 1)
{
printf("no solution\n");
return 0;
}
for(int i = 1; i <= n; ++i) fat[i] = i;
for(int i = 1; i <= tot; ++i)
{
int u = Find(ans[i].x);
int v = Find(ans[i].y);
if(u != v) fat[u] = v;
}
num = tot;
if(num != k)
for(int i = 1; i <= m; ++i)
if(!a[i].z)
{
int u = Find(a[i].x);
int v = Find(a[i].y);
if(u != v)
{
++num;
fat[u] = v;
ans[++tot] = a[i];
if(num == k) break;
}
}
if(num != k)
{
printf("no solution\n");
return 0;
}
for(int i = 1; i <= m; ++i)
if(a[i].z)
{
int u = Find(a[i].x);
int v = Find(a[i].y);
if(u != v)
{
fat[u] = v;
ans[++tot] = a[i];
if(tot == n - 1) break;
}
}for(int i = 1; i <= tot; ++i)
printf("%d %d %d\n", ans[i].x, ans[i].y, ans[i].z);
}
原文：http://www.cnblogs.com/lytccc/p/6221493.html