题面
首先两点之间的安全系数就是两点之间的最小割
于是乎搞出最小割树，然后安全系数从大到小合并带权并查集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
using namespace std;
int s, t, n, m, q;
struct edge {
int v, f, nxt;
} e[6010];
int head[610], tot = 1;
inline void addedge(int u, int v, int f) {
e[++tot] = edge{v, f, head[u]};
head[u] = tot;
e[++tot] = edge{u, f, head[v]};
head[v] = tot;
}
int level[610], cur[610];
inline int bfs() {
queue<int> q;
memset(level, 0, sizeof level);
level[s] = 1;
q.push(s);
memcpy(cur, head, sizeof(cur));
while(!q.empty()) {
int now = q.front();
q.pop();
for(int i = head[now]; i; i = e[i].nxt) {
if(level[e[i].v] == 0 && e[i].f) level[e[i].v] = level[now] + 1, q.push(e[i].v);
if(e[i].v == t && e[i].f) return 1;
}
}
return 0;
}
inline int dfs(int now, int limit) {
if(now == t) return limit;
int ans = 0;
for(int &i = cur[now]; i; i = e[i].nxt) {
if(e[i].f == 0 || level[e[i].v] != level[now] + 1) continue;
int lala = dfs(e[i].v, min(limit, e[i].f));
limit -= lala;
ans += lala;
e[i].f -= lala;
e[i ^ 1].f += lala;
if(limit == 0) return ans;
}
return ans;
}
struct node {
int u, v, w;
friend inline int operator < (const node &a, const node &b) {
return a.w > b.w;
}
} nd[610];
int cnt;
inline int dinic() {
for(int i = 2; i <= tot; i += 2) e[i].f = e[i ^ 1].f = e[i].f + e[i ^ 1].f >> 1;
int ans = 0;
while(bfs()) ans += dfs(s, 1000000);
return ans;
}
inline void solve(vector<int> &v) {
if(v.size() < 2) return;
s = v[0], t = v[1];
vector<int> v1, v2;
nd[++cnt] = node{s, t, dinic()};
for(int i : v) {
if(level[i] == 0) v1.push_back(i);
else v2.push_back(i);
}
v.clear();
solve(v1), solve(v2);
}
struct query {
int k, id;
friend inline int operator < (const query &a, const query &b) {
return a.k < b.k;
}
} qe[2030];
int ans[2030];
int fa[610];
inline int gf(int a) {return fa[a] < 0 ? a : fa[a] = gf(fa[a]);}
inline int merge(int a, int b) {
a = gf(a), b = gf(b);
if(a == b) return -fa[a];
fa[a] += fa[b];
fa[b] = a;
return -fa[a];
}
int main() {
scanf("%d%d%d", &n, &m, &q);
int maxs = 0;
for(int i = 1; i <= n; i++) scanf("%d", fa + i), fa[i] = -fa[i], maxs = max(maxs, -fa[i]);
for(int i = 1, u, v; i <= m; i++) scanf("%d%d", &u, &v), addedge(u, v, 1);
vector<int> v;
for(int i = 1; i <= n; i++) v.push_back(i);
solve(v);
for(int i = 1; i <= q; i++) scanf("%d", &qe[i].k), qe[i].id = i;
sort(nd + 1, nd + 1 + cnt);
sort(qe + 1, qe + 1 + q);
for(int i = 1, j = 1; i <= q; i++) {
while(maxs < qe[i].k) {
if(j == cnt + 1) break;
maxs = max(maxs, merge(nd[j].u, nd[j].v));
j++;
}
if(maxs < qe[i].k) ans[qe[i].id] = -2;
else if(j == 1) ans[qe[i].id] = -1;
else ans[qe[i].id] = nd[j - 1].w;
}
for(int i = 1; i <= q; i++)
if(ans[i] == -1) puts("nan");
else if(ans[i] == -2) puts("Nuclear launch detected");
else printf("%d\n", ans[i]);
return 0;
}