点击查看代码
#include<bits/stdc++.h>
#define int long long
#define Blue_Archive return 0
#define con putchar(' ')
#define ent putchar('\n')
using namespace std;
constexpr int N = 5e5 + 7;
constexpr int M = 8e5 + 7;
constexpr int INF = 1e18;int n;
int m;
int s;
int t;
int tot = 1;
int ans;
int a[N];
int b[N];
int c[N];
int h[N];
int w[M];
int to[M];
int nxt[M];
int dis[N];
int cur[N];queue<int> q;inline int read()
{int x = 0,k = 1;char op = getchar();while(op > '9' || op < '0'){if(op == '-') k = -1;op = getchar();} while(op <= '9' && op >= '0') x = (x << 1) + (x << 3) + op - '0',op = getchar();return x * k;
}inline void write(int x)
{if(x < 0) x = -x,putchar('-');if(x > 9) write(x / 10);putchar(x % 10 + '0');
}inline void add(int a,int b,int c)
{to[++ tot] = b,w[tot] = c,nxt[tot] = h[a],h[a] = tot;to[++ tot] = a,w[tot] = 0,nxt[tot] = h[b],h[b] = tot;
}inline bool bfs()
{for(int i = 1;i <= t;i ++) dis[i] = INF;queue<int> q;q.push(s);dis[s] = 0;cur[s] = h[s];while(!q.empty()){int u = q.front();q.pop();for(int i = h[u];i;i = nxt[i]){if(w[i] && dis[to[i]] == INF){q.push(to[i]);cur[to[i]] = h[to[i]];dis[to[i]] = dis[u] + 1;if(to[i] == t) return 1;}}}return 0;
}inline int dfs(int x,int sum)
{if(x == t) return sum;int k,res = 0;for(int i = cur[x];i && sum;i = nxt[i]){cur[x] = i;if(w[i] && dis[to[i]] == dis[x] + 1){k = dfs(to[i],min(sum,w[i]));if(k == 0) dis[to[i]] = INF;w[i] -= k;w[i ^ 1] += k;res += k;sum -= k;}} return res;
}signed main()
{// freopen("data.in","r",stdin);freopen("data.out","w",stdout);n = read();m = read();s = n + 1;t = n + 2;for(int i = 1;i <= n;i ++) a[i] = read(),add(s,i,a[i]);for(int i = 1;i <= n;i ++) b[i] = read(),add(i,t,b[i]);for(int i = 1,u,v,w;i <= m;i ++){u = read();v = read();w = read();add(u,v,w);add(v,u,w);}while(bfs()) ans += dfs(s,INF);write(ans);ent;Blue_Archive;
}
