目录

  1. 引言
  2. BZOJ 3712: [PA2014]Fiolki
    1. Description
    2. Input
    3. Output
    4. Sample Input
    5. Sample Output
    6. Source
    7. 题目分析
    8. 代码

引言

BZOJ 3712: [PA2014]Fiolki 题解

BZOJ 3712: [PA2014]Fiolki

  • Time Limit: 30 Sec

  • Memory Limit: 128 MB

Description

化学家吉丽想要配置一种神奇的药水来拯救世界。
吉丽有n种不同的液体物质,和n个药瓶(均从1到n编号)。初始时,第i个瓶内装着g[i]克的第i种物质。吉丽需要执行一定的步骤来配置药水,第i个步骤是将第a[i]个瓶子内的所有液体倒入第b[i]个瓶子,此后第a[i]个瓶子不会再被用到。瓶子的容量可以视作是无限的。
吉丽知道某几对液体物质在一起时会发生反应产生沉淀,具体反应是1克c[i]物质和1克d[i]物质生成2克沉淀,一直进行直到某一反应物耗尽。生成的沉淀不会和任何物质反应。当有多于一对可以发生反应的物质在一起时,吉丽知道它们的反应顺序。每次倾倒完后,吉丽会等到反应结束后再执行下一步骤。
吉丽想知道配置过程中总共产生多少沉淀。

Input

第一行三个整数n,m,k(0<=m<n<=200000,0<=k<=500000),分别表示药瓶的个数(即物质的种数),操作步数,可以发生的反应数量。
第二行有n个整数g[1],g[2],…,g[n](1<=g[i]<=10^9),表示初始时每个瓶内物质的质量。
接下来m行,每行两个整数a[i],bi,表示第i个步骤。保证a[i]在以后的步骤中不再出现。
接下来k行,每行是一对可以发生反应的物质c[i],di,按照反应的优先顺序给出。同一个反应不会重复出现。

Output

所求答案

Sample Input

3 2 1

2 3 4

1 2

3 2

2 3

Sample Output

6

Source

鸣谢Jcvb

题目分析

一道思维好题

一开始我还用并查集+set+启发式合并,结果直接TLE……虽然卡卡常也许能过,但是没有必要了对吧

我们发现,整个实验过程可以看成一棵树的结构,一开始,每瓶药剂都是单独的点,我们做一次实验,就合并两个点,相当于新建一个点作为他们的父亲,然后这个父亲继续参与反应

这样,我们可以建出树

然后,两个反应最近的反应时间,就是它们的LCA,我们知道,每对药剂最多只会反应一次,因为不会只倒出部分药剂,所以我们把每对可能反应按照发生时间排序再做一遍,同时发现当前反应未发生就直接跳出即可

其实还是有一些细节

代码

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cassert>
#define ll long long int
#define maxn 600005 //注意开够内存
#define bit 20
#define erep(i, x) for (register int i = h[x]; i; i = e[i].next)
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
#define gc() ((p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, maxn, stdin), p1 == p2)) ? EOF : *p1++)
using namespace std;
char *p1, *p2;
char buffer[maxn];
template <class T> void read(T& x){
char ch = gc(); x = 0; bool f = 1;
while (!('0' <= ch && ch <= '9') && ch != '-') ch = gc();
if (ch == '-') f = 0, ch = gc();
while ('0' <= ch && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = gc();
if (!f) x = -x;
}
int n, m, k, ct = 0;
int g[maxn];
int now[maxn];
struct edge{
int next, to;
edge(int next, int to) : next(next), to(to){}
edge(){}
}e[maxn << 1];
int h[maxn], cnt = 1;
void Add_Edge(int x, int y){
e[++cnt] = edge(h[x], y);
h[x] = cnt;
e[++cnt] = edge(h[y], x);
h[y] = cnt;
}
int fa[maxn][bit + 1];
int d[maxn];
void DFS(int x){
rep(i, 1, bit) fa[x][i] = fa[fa[x][i - 1]][i - 1];
erep(i, x){
int op = e[i].to;
if (op == fa[x][0]) continue;
fa[op][0] = x;
d[op] = d[x] + 1;
DFS(op);
}
}
int get_lca(int x, int y){
if (x == y) return x;
if (d[x] < d[y]) swap(x, y);
int k = d[x] - d[y], now = 0;
while (k){
if (k & 1) x = fa[x][now];
now++, k >>= 1;
}
if (x == y) return x;
per(i, bit, 0) if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
struct ope{
int x, y, t, id;
ope(int x = 0, int y = 0, int t = 0, int id = 0) : x(x), y(y), t(t), id(id){}
bool operator < (const ope b) const{
return (t == b.t) ? id < b.id : (d[t] == d[b.t]) ? t < b.t : d[t] > d[b.t];
//return (t == b.t) ? id < b.id : d[t] > d[b.t]; 这样写是不对的,因为有可能出现循环比较
}
}line[maxn];
int main(){
#ifndef ONLINE_JUDGE
freopen("fiolki.in", "r", stdin);
#endif
int x, y;
read(n), read(m), read(k);
rep(i, 1, n) read(g[i]), now[i] = i;
ct = n;
rep(i, 1, m){
read(x), read(y);
++ct;
if (!now[x] || !now[y]) assert(false);
Add_Edge(now[x], ct);
Add_Edge(now[y], ct);
now[x] = 0, now[y] = ct;
}
++ct;
rep(i, 1, n) if (now[i]) Add_Edge(ct, now[i]);
DFS(ct);
rep(i, 1, k){
read(x), read(y);
int lca = get_lca(x, y);
line[i] = ope(x, y, lca, i);
}
sort(line + 1, line + 1 + k);
ll ans = 0;
rep(i, 1, k){
if (line[i].t == ct) break;
x = line[i].x, y = line[i].y;
int mi = min(g[x], g[y]);
g[x] -= mi, g[y] -= mi, ans += mi << 1;
}
printf("%lld", ans);
return 0;
}