洛谷题单指南-最小生成树-P3623 [APIO2008] 免费道路
原题链接：https://www.luogu.com.cn/problem/P3623
题意解读：n个节点m条边的无向图，其中边有两种类似，一种是“水泥路”，一种是“鹅卵石路”，要求一种生成树方案，正好将n个节点连通，且“鹅卵石路”条数正好是k条。
解题思路：
1、问题分析
由于限制鹅卵石路的条数，而鹅卵石路可以分为两种：
必选的，如果不选则整个图无法连通
非必选的，可以用其他水泥路来代替
思路就是先确定哪些鹅卵石路必选，然后在其余鹅卵石路中继续选择凑足k个，再去水泥路中选择正好能将整个图连通的边。
2、算法思路
类似kruskal算法
先枚举所有水泥路，尽可能的选择能连通各个节点的边，计算出一共选了多少条边，离n-1条边的差距就是必选的鹅卵石路条数。
再枚举所有鹅卵石路，选择边将上一步未连通的部分连通，保存已选择的边。
清空并查集，重新执行类kruskal算法，先加入必选的鹅卵石路。
再枚举其余鹅卵石路，将能导致连通的边加入，凑足k个。如果最终鹅卵石路不足k个，表示无解。
最后枚举水泥路，将所有能导致连通的边加入。如果最终选择的所有边不如n-1，表示无解。
100分代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 20005, M = 100005;
struct Edge
{
int u, v, type;
} edges[M];
int p[N];
vector<int> ans;
int n, m, k;
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
void init()
{
for(int i = 1; i <= n; i++) p[i] = i;
}
int main()
{
cin >> n >> m >> k;
for(int i = 1; i <= m; i++)
{
cin >> edges[i].u >> edges[i].v >> edges[i].type;
}
//将可带来连通的水泥路连通
init();
for(int i = 1; i <= m; i++)
{
if(edges[i].type == 1)
{
int a = find(edges[i].u);
int b = find(edges[i].v);
if(a != b)
{
p[a] = b;
}
}
}
//将可带来连通的鹅卵石路连通，并记录，表示必须要选的鹅卵石路
for(int i = 1; i <= m; i++)
{
if(edges[i].type == 0)
{
int a = find(edges[i].u);
int b = find(edges[i].v);
if(a != b)
{
p[a] = b;
ans.push_back(i);
}
}
}
//清空并查集，将必须加入的鹅卵石路连通
init();
for(int i = 0; i < ans.size(); i++)
{
int a = find(edges[ans[i]].u);
int b = find(edges[ans[i]].v);
p[a] = b;
}
//继续加入鹅卵石路，凑足k个
for(int i = 1; i <= m; i++)
{
if(edges[i].type == 0)
{
int a = find(edges[i].u);
int b = find(edges[i].v);
if(a != b)
{
p[a] = b;
ans.push_back(i);
if(ans.size() >= k) break;
}
}
}
if(ans.size() < k)
{
cout << "no solution";
return 0;
}
//加入水泥路
for(int i = 1; i <= m; i++)
{
if(edges[i].type == 1)
{
int a = find(edges[i].u);
int b = find(edges[i].v);
if(a != b)
{
p[a] = b;
ans.push_back(i);
}
}
}
//如果图不连通
if(ans.size() != n - 1) cout << "no solution";
else
{
for(int i = 0; i < ans.size(); i++)
cout << edges[ans[i]].u << " " << edges[ans[i]].v << " " << edges[ans[i]].type << endl;
}
return 0;
}