网络流裸题
\(s\)向点连边\((s, i, a[i])\)
给每个边建一个点
边\((u, v, w)\)抽象成\((u, E, inf)\)和\((v, E, inf)\)以及边\((E, t, w)\)
最小割建模...
然后就没了....复习一下板子吧
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define ll long long
#define ri register int
#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)
#define drep(io, ed, st) for(ri io = ed; io >= st; io --)
#define gc getchar
inline int read() {
int p = 0, w = 1; char c = gc();
while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); }
while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc();
return p * w;
}
const int sid = 5e4 + 5;
const ll inf = 1e17;
int n, m, s, t, ip, cnp = 1;
int a[sid], q[sid], go[sid], num[sid], L[sid];
int cap[sid], nxt[sid], node[sid];
ll res[sid];
inline void addedge(int u, int v, ll w) {
nxt[++ cnp] = cap[u]; cap[u] = cnp; node[cnp] = v; res[cnp] = w;
nxt[++ cnp] = cap[v]; cap[v] = cnp; node[cnp] = u; res[cnp] = 0;
}
#define cur node[i]
inline void bfs() {
int fr = 1, to = 0;
L[t] = 1; num[1] ++; q[++ to] = t;
while(fr <= to) {
int o = q[fr ++];
for(int i = cap[o]; i; i = nxt[i])
if(res[i ^ 1] && !L[cur]) {
q[++ to] = cur;
L[cur] = L[o] + 1; num[L[cur]] ++;
}
}
for(int i = 1; i <= t; i ++) go[i] = cap[i];
}
inline ll dfs(int o, ll flow) {
ll tt = 0, tmp;
if(o == t) return flow;
for(int &i = go[o]; i; i = nxt[i]) {
if(L[cur] + 1 != L[o]) continue;
tmp = dfs(cur, min(flow, res[i]));
res[i] -= tmp; res[i ^ 1] += tmp;
flow -= tmp; tt += tmp;
if(!flow) return tt;
}
-- num[L[o]]; if(!num[L[o]]) L[s] = t + 1;
L[o] ++; num[L[o]] ++;
go[o] = cap[o];
return tt;
}
inline ll isap(int s, int t) {
bfs();
ll ret = dfs(s, inf);
while(L[s] <= t) ret += dfs(s, inf);
return ret;
}
int main() {
ll ans = 0;
n = read(); m = read();
rep(i, 1, n) a[i] = read();
s = n + m + 1; t = s + 1;
rep(i, 1, n) addedge(s, i, a[i]);
rep(i, 1, m) {
int u = read(), v = read(), w = read();
addedge(u, n + i, inf); addedge(v, n + i, inf);
addedge(n + i, t, w); ans += w;
}
ans -= isap(s, t);
printf("%lld\n", ans);
return 0;
}