洛谷P3623题解
原题
P3623 [APIO2008]免费道路
思路概述
题意分析
给定 \(n\) 个结点， \(m\) 条无向边，其中有水泥路和石子路。求该图的生成树，并要求其中含 \(k\) 条石子路。若存在合法的生成树，则输出任意构造方案；反之则输出字符串"no solution"。
思路分析
自由之路
本题涉及图中的生成树问题，所以首先考虑Kruskal算法。但由于选特殊边的过程中会破坏生成树的结构，显然一次Kruskal算法不能解决问题，考虑多次运行求必要边，最后在其余边中继续选取其他边。
算法实现
关于必要边
在展开内容前，笔者决定先简要说明什么是必要边。
下图中，即使所有边权为 \(1\) 的边全部连上，只要全图联通，则必须连红框中的一边。对于这种无论何种方式都需要连的边我们称其为必要边。
这种边的求法也很简单，只需要将另一种边全部连上，再连当前种类的边，而此时连的边则都为必要边。本题中只需要求石子路中的必要边，即先连水泥路，再连石子路，此时连的石子路都是必要边。
多次Kruskal的具体实现
将所有无向边按边权（种类）从小到大排序，便于优先选取石子路连边
首先，必要边肯定应该存在于答案中，所以在求必要边时就直接打上标记。
求出必要边后，再依次考虑每一条石子路能不能加进去，直到凑够 \(k\) 条石子路。
最后用剩余的水泥路将图完全连通为生成树。
一些细节
数据中可能出现 \(k>cnt_{stone}\) 的情况，所以读入时先记录石子路数量。
连石子路时一定注意满足 \(cnt_{stone}
码量不大，但是重复内容很多，建议分块检查调试。一定不要复制之前的代码片段。
AC code
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define RI register int
using namespace std;
const int maxn=2e5+10;
typedef struct
{
int u,v;
bool type,mark;/*type表示道路类型 mark表示是否选取*/
inline void output(void)/*懒得打代码 封装输出模块*/
{
cout << u << " " << v << " " << type << endl;
return;
}
}side;
typedef struct
{
int pre,dep;
inline void init(int x)
{
pre=x;dep=1;
return;
}
}node;
side s[maxn];
node e[maxn];
int n,m,k,cnt,tot,brd;
inline bool cmp(side x,side y);/*边权排序*/
inline void init(int x);/*并查集初始化*/
inline int find(int x);/*祖先查询*/
inline void merge(int x,int y);/*并查集结点合并*/
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> n >> m >> k;
for(RI i=1;i<=m;++i)
{
cin >> s[i].u >> s[i].v >> s[i].type;
brd+=(!s[i].type);/*记录石子路数量*/
}
sort(s+1,s+m+1,cmp);init(n);
/*优先连水泥路 求必要石子路*/
for(RI i=brd+1;i<=m;++i) if(find(s[i].u)!=find(s[i].v)) merge(s[i].u,s[i].v);
for(RI i=1;i<=brd && cnt