Luogu5687 [CSP-SJX2019]网格图

tony102

2020 年 12 月 03 日

1233 次浏览

暂无评论

505字数

题解

[Link](https://www.luogu.com.cn/problem/P5687)

## Sol

不得不说,虽然JX的同学去年得再考一次联赛,但是同样的报名费,获得了一次翻盘机会,而且这套题的质量也不知道比CSP2019的好到哪里去了

首先64分很好拿,直接Kruskal板子上去就好了

然后你再观察,发现你要是棵生成树,在这样的网格图中会选一段对答案优的横边或者竖边(主要是要强调一段)

用Kruskal的板子把选的边打印出来,你会发现Kruskal选的边一定是权值小的一段一段的出现.

所以就把横边的权值和竖边的权值排序,每次选一排或一列的就可以了.注意这么选是要保证无环的.

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 3e5 + 5;

int n, m, num;
int a[SIZE], b[SIZE];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

inline int cmp(int a, int b) { return a < b; }

signed main() {
	// freopen("code.in", "r", stdin);
	// freopen("code.out", "w", stdout);
	n = read(), m = read();
	for (int i = 1; i <= n; ++ i) a[i] = read();
	for (int i = 1; i <= m; ++ i) b[i] = read();
	std::sort(a + 1, a + n + 1, cmp); std::sort(b + 1, b + m + 1, cmp);
	int ans = (m - 1) * a[1] + (n - 1) * b[1];
	int p = 1, q = 1, cnt1 = 2, cnt2 = 2;
	while (cnt1 <= n && cnt2 <= m) {
		if (a[cnt1] <= b[cnt2]) ans += (a[cnt1 ++] * (m - q)), ++ p;
		else ans += (b[cnt2 ++] * (n - p)), ++ q;
	}
	printf("%lld\n", ans);
	return 0;
}
```

###

最后修改：2021 年 09 月 04 日