【luogu P3623 [APIO2008]免费道路】 题解

题目链接：https://www.luogu.org/problemnew/show/P3623

说是对克鲁斯卡尔的透彻性理解

正解：

先考虑加入水泥路，然后再考虑加入剩下必须要加入的最少鹅卵石路。

之后对原图再跑最小生成树

先跑鹅卵石路到k条。

再从所有水泥路中直到成为最小生成树。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 100000 + 10;

int n, m, k, fa[maxn], cnt, shuini, eluan, tot;

bool f[maxn];

struct edge{

	int u, v, w;

}e[maxn<<2], ans[maxn<<2];

bool cmp(edge a, edge b)

{

	return a.w < b.w;

}

int find(int x)

{

	return fa[x] == x ? x : fa[x] = find(fa[x]);

}

int main()

{

	scanf("%d%d%d",&n,&m,&k);

	for(int i = 1; i <= n; i++) fa[i] = i;

	for(int i = 1; i <= m; i++)

	{

		int opt;

		scanf("%d%d%d",&e[i].u, &e[i].v, &opt);

		if(opt == 0) e[i].w = 1, eluan++;

		else e[i].w = 0, shuini++;

	}

	if(eluan < k)

	{

		cout<<"no solution\n";

		return 0;

	}

	sort(e+1, e+1+m, cmp);

	for(int i = 1; i <= shuini; i++)

	{

		if(cnt == n-1) break;

		int rx, ry;

		rx = find(e[i].u), ry = find(e[i].v);

		if(rx != ry)

		{

			fa[ry] = rx;

			cnt++;

		}

	}

	int eluanmust = 0;

	for(int i = shuini+1; i <= m; i++)

	{

		if(cnt == n-1) break;

		int rx, ry;

		rx = find(e[i].u), ry = find(e[i].v);

		if(rx != ry)

		{

			fa[ry] = rx;

			f[i] = 1, eluanmust++;

			cnt++;

		}

	}

	if(cnt != n-1 || eluanmust > k)

	{

		cout<<"no solution\n";

		return 0;

	}

	for(int i = 1; i <= n; i++) fa[i] = i;

	cnt = 0;

	for(int i = shuini+1; i <= m; i++)

	{

		if(cnt == n-1) break;

		if(f[i] == 1)

		{

			int rx, ry;

			rx = find(e[i].u), ry = find(e[i].v);

			fa[ry] = rx;

			cnt++;

			ans[++tot].u = e[i].u;

			ans[tot].v = e[i].v;

			ans[tot].w = e[i].w^1;

			//printf("%d %d %d\n",e[i].u, e[i].v, e[i].w^1);

		}

	}

	for(int i = shuini+1; i <= m; i++)

	{

		if(cnt == k) break;

		int rx, ry;

		rx = find(e[i].u), ry = find(e[i].v);

		if(rx != ry)

		{

			fa[ry] = rx;

			cnt++;

			ans[++tot].u = e[i].u;

			ans[tot].v = e[i].v;

			ans[tot].w = e[i].w^1;

			//printf("%d %d %d\n",e[i].u, e[i].v, e[i].w^1);

		}

	}

	if(cnt < k)

	{

		cout<<"no solution\n";

		return 0;

	}

	for(int i = 1; i <= shuini; i++)

	{

		if(cnt == n-1) break;

		int rx, ry;

		rx = find(e[i].u), ry = find(e[i].v);

		if(rx != ry)

		{

			fa[ry] = rx;

			cnt++;

			ans[++tot].u = e[i].u;

			ans[tot].v = e[i].v;

			ans[tot].w = e[i].w^1;

			//printf("%d %d %d\n",e[i].u, e[i].v, e[i].w^1);

		}

	}

	if(cnt != n-1)

	{

		cout<<"no solution\n";

		return 0;

	}

	for(int i = 1; i <= tot; i++)

	printf("%d %d %d\n",ans[i].u, ans[i].v, ans[i].w);

	return 0;

}