「Usaco2008 Oct」灌水 - 最小生成树

氵一篇 Blog

Shq 只会刷水题了 /kel

题目链接

1601. [Usaco2008 Oct]灌水

Description

Farmer John 已经决定把水灌到他的 n(1n300)n(1\le n\le 300) 块农田,农田被数字 11nn 标记。把一块土地进行灌水有两种方法,从其他农田饮水,或者这块土地建造水库

建造一个水库需要花费 wi(1wi105)w_i(1\le w_i\le10^5) , 连接两块土地需要花费Pij(1pij105,pij=pji,pii=0)P_{ij}(1\le p_{ij}\le10^5,p_{ij}=p_{ji},p_{ii}=0). 计算 Farmer John 所需的最少代价。

Input

*第一行:一个数 nn

*第二行到第 n+1n+1 行:第 i+1i+1 行含有一个数 wiw_i

*第 n+2n+2 行到第 2n+12n+1 行:第 n+1+in+1+i 行有 nn 个被空格分开的数,第 jj 个数代表 pijp_{ij}

Output

*第一行:一个单独的数代表最小代价.

Sample Input

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

Sample Output

1
9

输出详解:

Farmer John在第四块土地上建立水库,然后把其他的都连向那一个,这样就要花费 3+2+2+2=93+2+2+2=9


题解

sb 最小生成树题

建一个点向所有点连一条权值为 wiw_i 的边

剩下的按照题目来就好了(

Code

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
struct Edge {
int to, dist;
int from;

Edge () {}
Edge (int _from, int _to, int _dist) : from(_from) , to(_to) , dist(_dist) {}

~Edge () {}

bool operator < (const Edge &other)const {
return dist < other.dist;
}
};

const int MAXN = 100010;

int tot;
Edge edges[MAXN];

inline void addEdge (int u, int v, int w) {
edges[tot++] = Edge(u, v, w);
}

ll n;
ll data[MAXN];

int fa[MAXN];

inline void init () {
up (i, 1, n) fa[i] = i;
}

inline int find (int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}

inline void merge (int x, int y) {
fa[x] = y;
}

int main(int argc, char const *argv[]) {
srand(time(NULL) + rand()); srand(time(NULL) + rand() + rand() * rand()); srand(time(NULL) + rand() + rand() ^ rand() * rand());
while (rand() & 1) n = rand() * rand();
n = SlowRead();

ll tmp = n + 1;

up (i, 1, n) data[i] = SlowRead();

int w;
up (u, 1, n)
up (v, 1, n) {
w = SlowRead();
addEdge (u, v, w);
}

up (i, 1, n) addEdge (i, tmp, data[i]);

std::sort (edges, edges + tot);

init();

int ans = 0;
up (i, 0, tot - 1) {
//printf("%d->%d is %d\n", edges[i].from, edges[i].to, edges[i].dist);
int fx = find(edges[i].from);
int fy = find(edges[i].to);
if (fx != fy) {
merge (fx, fy);
ans += edges[i].dist;
}
}

Print(ans);
return 0;
}

谜之音:那么氵的题目还氵 Blog(

本文是 2019/1/9 20:58 写完的,不知道啥时候能发出去(

img

坚持原创技术分享,您的支持将鼓励我继续创作!