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
113
114
115
116
117
118
119
120
121
122
123
124
125
| #include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> PII;
const int MAX_N = 2e5 + 10, INF = 1e9 + 7, mod = 998244353;
namespace Dinic {
using ll = long long;
const int MAX_V = 2e4 + 10;
struct Edge {
int from, to;
ll cup, flow;
Edge(int u, int v, ll c, ll f) : from(u), to(v), cup(c), flow(f) {}
};
struct Graph {
int s, t, n, m;
vector<Edge> es;
vector<int> G[MAX_V];
int level[MAX_V], iter[MAX_V];
bool vis[MAX_V];
Graph(int s, int t, int n = MAX_V) : n(n), s(s), t(t) {
es.clear();
for(int i = 0; i < n; i ++) {
G[i].clear();
}
};
void addEdge(int u, int v, ll c) {
es.push_back({u, v, c, 0}), es.push_back({v, u, 0, 0});
m = es.size();
G[u].push_back(m - 2), G[v].push_back(m - 1);
}
ll dfs(int v, ll f) {
if(v == t || f == 0) return f;
ll flow = 0, d;
for(int &i = iter[v]; i < G[v].size(); i ++) {
auto &e = es[G[v][i]], &reve = es[G[v][i] ^ 1];
if(level[v] + 1 == level[e.to] && (d = dfs(e.to, min(f, e.cup - e.flow))) > 0) {
e.flow += d, reve.flow -= d;
flow += d;
f -= d;
if(! f) break;
}
}
return flow;
}
bool bfs() {
memset(vis, false, sizeof vis);
queue<int> q;
q.push(s);
level[s] = 0;
vis[s] = true;
while(q.size()) {
int v = q.front();
q.pop();
for(int i = 0; i < G[v].size(); i ++) {
auto &e = es[G[v][i]], &reve = es[G[v][i] ^ 1];
if(!vis[e.to] && e.cup > e.flow) {
vis[e.to] = true;
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
return vis[t];
}
ll maxflow() {
ll flow = 0;
while(bfs()) {
memset(iter, 0, sizeof iter);
flow += dfs(s, INF);
}
return flow;
}
};
};
using namespace Dinic;
void solve() {
int n, m, k;
cin >> n >> m >> k;
int s = 0, t = 2e4 + 1;
Graph gra(s, t);
vector<int> a(n + 1);
vector<int> cur(n + 1);
for(int i = 1; i <= n; i ++) {
cin >> a[i];
gra.addEdge(s, i, 1);
cur[i] = i;
}
int id = n + 1;
for(int i = 1; i <= m; i ++) {
int x, y;
cin >> x >> y;
int n1 = cur[x], n2 = cur[y];
gra.addEdge(n1, n2, 1);
gra.addEdge(n2, n1, 1);
gra.addEdge(n1, cur[x] = id ++, a[x]);
gra.addEdge(n2, cur[y] = id ++, a[y]);
}
for(int i = 0; i < k; i ++) {
int x;
cin >> x;
int mp = cur[x];
gra.addEdge(mp, t, a[x]);
}
cout << gra.maxflow() << '\n';
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
int _ = 1;
cin >> _;
while(_ --) {
solve();
}
}
|