洛谷P1621《集合》

二月 04, 2019 3003

素数筛 + 并查集

题目背景

John的农场缺水了！！！

题目描述

Farmer John has decided to bring water to his N (1 <= N <= 300) pastures which are conveniently numbered 1..N. He may bring water to a pasture either by building a well in that pasture or connecting the pasture via a pipe to another pasture which already has water.

Digging a well in pasture i costs W_i (1 <= W_i <= 100,000).

Connecting pastures i and j with a pipe costs P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0).

Determine the minimum amount Farmer John will have to pay to water all of his pastures.

POINTS: 400

农民John 决定将水引入到他的n(1<=n<=300)个牧场。他准备通过挖若

干井，并在各块田中修筑水道来连通各块田地以供水。在第i 号田中挖一口井需要花费W_i(1<=W_i<=100,000)元。连接i 号田与j 号田需要P_ij (1 <= P_ij <= 100,000 , P_ji=P_ij)元。

请求出农民John 需要为使所有农场都与有水的农场相连或拥有水井所需要的钱数。

输入输出格式

输入格式

第1 行为一个整数n。

第2 到n+1 行每行一个整数，从上到下分别为W_1 到W_n。

第n+2 到2n+1 行为一个矩阵，表示需要的经费（P_ij）。

输出格式

只有一行，为一个整数，表示所需要的钱数。

输入输出样例

输入样例

1
2
3
4
5
6
7
8
9
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

输出样例

1
9

说明

John等着用水，你只有1s时间！！！

解题思路

题目中“质数”两个字很是显眼啊

还等啥啊

筛啊

素数筛很好写吧

筛完了，然后呢？

题目让我们找两个公共质因数 \geq P 的，不在一个集合里的数，并合并它们。我们不这样找

枚举每一个质数primes[i]，计算出第一个 大于A的primes[i]的倍数（题目要求的）记为 t ，然后从 t+\text{primes[i]} 一直枚举到 B （每次增长一个 \text{primes[i]} ，毕竟要求必须有 \text{primes[i]} 这个数作为质因数），每次用并查集合并 t 和当前枚举到的这个数

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;
using std::max;

const int MAXB = 100000 + 10;

int A, B, P;

int primes[MAXB], cnt, ans;
bool npm[MAXB]; // n(ot a )p(ri)m(e) -> not a prime

int U[MAXB];

int Find(int x) {
	if (U[x] == x) return x;
	return U[x] = Find(U[x]);
}

inline void Union(int x, int y) {
	x = Find(x), y = Find(y);
	if (x == y) return;
	--ans; // 两个集合变成了一个，答案减一
	U[x] = y;
}

int main() {
    IMPROVE_IO();
    cin >> A >> B >> P;
	for (int i = 1; i <= B; ++i) U[i] = i; // 并查集初始化
    // 筛一波素数
    for (int i = 2; i <= B; ++i) {
    	if (!npm[i]) primes[++cnt] = i;
    	for (int j = 1; j <= cnt && primes[j] * i <= B; ++j) {
    		npm[primes[j] * i] = true;
    		if (i % primes[j] == 0) break;
		}
	}
	ans = B - A + 1; // r - l + 1
    // 原来的答案总数是（右边界 - 左边界 + 1）
    //（即 B - A + 1），每次合并集合的时候两个集合变成了一个，--ans
	for (int i = 1; i <= cnt; ++i) {
		if (primes[i] < P) continue; // 质因数要求大于等于P
		int np = (A + primes[i] - 1) / primes[i] * primes[i];
		// np -> The smallest multiple of primes[i] larger than A
        // np -> 最小的 比A大的 primes[i]的倍数
		for (int j = np + primes[i]; j <= B; j += primes[i]) {
			Union(np, j); 
		}
	} 
	cout << ans << endl;
    return 0;
}