题解【洛谷P2323】 [HNOI2006]公路修建问题

题解

跑两遍\(Kruskal\)，第一次找出\(k\)条一级公路，第二次找出\(n - k - 1\)条二级公路，直接计算\(MST\)的权值之和即可。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cctype>

#define gI gi

#define itn int

#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)

using namespace std;

inline int gi()

{

    int f = 1, x = 0; char c = getchar();

    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}

    while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}

    return f * x;

}

int n, m, fa[20003], k, vis[20003];

struct OIer

{

	int a, b, c1, c2, id;

} d[20003];

struct STO_Tham

{

	int Id, Tham;

} ans[20003];

int getf(int u)

{

	if (fa[u] == u) return u;

	return fa[u] = getf(fa[u]);

}

int maxx = 900000000, maxy, tot;

inline bool cmp(OIer x, OIer y) {return x.c1 < y.c1;}

inline bool cmp1(OIer x, OIer y) {return x.c2 < y.c2;}

inline bool OrzTham(STO_Tham x, STO_Tham y) {return x.Id < y.Id;}

int main()

{

	//File("P2323");

	n = gi(), k = gi(), m = gi(); --m;

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

	{

		d[i].a = gi(), d[i].b = gi(), d[i].c1 = gi(), d[i].c2 = gi(), d[i].id = i;

	}

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

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

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

	{

		int u = getf(d[i].a), v = getf(d[i].b);

		if (u != v)

		{

			fa[u] = v;

			ans[++tot].Id = d[i].id, ans[tot].Tham = 1;

			maxy = max(maxy, d[i].c1);

			if (tot == k) break;

		}

	}

	sort(d + 1, d + 1 + m, cmp1);

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

	{

		int u = getf(d[i].a), v = getf(d[i].b);

		if (u != v)

		{

			fa[u] = v;

			ans[++tot].Id = d[i].id, ans[tot].Tham = 2;

			maxy = max(maxy, d[i].c2);

			if (tot == n - 1) break;

		}

	}

	sort(ans + 1, ans + 1 + tot, OrzTham);

	printf("%d\n", maxy);

	for (int i = 1; i < n; i+=1) printf("%d %d\n", ans[i].Id, ans[i].Tham);

	return 0;

}

巴特西

题解【洛谷P2323】 [HNOI2006]公路修建问题

题解

代码

最新文章

热门文章