#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MAXV = 2e4 + 10; const int MAXE = 2e5 + 4e4 + 10; const int INF = 0x3f3f3f3f; int tmp; int src; int des; int cnt; int n;//sum of v int m;//sum of e struct Edge { int from, to; int next, cap; }edge[MAXE]; int head[MAXV]; int gap[MAXV], dep[MAXV], cur[MAXV], stack[MAXV], top; int iSap() { int curFlow, maxFlow, u, insert, i; memset(dep, 0, sizeof dep); memset(gap, 0, sizeof gap); memcpy(cur, head, n); maxFlow = 0; u = src; top = 0; while(dep[src] < n) { if(u == des) { curFlow = INF; for(i = 0;i < top; i++) { if(curFlow > edge[stack[i]].cap) { insert = i; curFlow = edge[stack[i]].cap; } } for(i = 0; i < top; i++) { edge[stack[i]].cap -= curFlow; edge[stack[i]^1].cap +=curFlow; } maxFlow += curFlow; u = edge[stack[top = insert]].from; } for(i = cur[u]; i!= -1; i = edge[i].next) { if((edge[i].cap > 0) && (dep[u] == dep[edge[i].to] + 1)) break; } if(i != -1) { stack[top++] = i; u = edge[i].to; } else { if(--gap[dep[u]] == 0) break; int minn = n; for(i = head[u]; i != -1; i = edge[i].next) { if(edge[i].cap > 0) minn = (minn > dep[edge[i].to])?(cur[u] = i, dep[edge[i].to]) : minn; } ++gap[dep[u] = minn + 1]; if(u != src) u = edge[stack[--top]].from; } } return maxFlow; } void addEdge(int u, int v, int f) { edge[cnt].next = head[u]; edge[cnt].from = u; edge[cnt].to = v; edge[cnt].cap = f; head[u] = cnt++; edge[cnt].next = head[v]; edge[cnt].from = v; edge[cnt].to = u; edge[cnt].cap = 0; head[v] = cnt++; } int main(void) { int fn, fm; while(scanf("%d%d", &fn, &fm) != EOF) { memset(head, -1, sizeof head); int a, b, c; cnt = src = 0, n = des = fn + 1; for(int i = 1; i <= fn; i++) { scanf("%d%d", &a, &b); addEdge(src, i, a); addEdge(i, src ,a); addEdge(des, i, b); addEdge(i, des, b); } for(int i = 0; i < fm; i++) { scanf("%d%d%d", &a, &b, &c); addEdge(a, b, c); addEdge(b, a, c); } printf("%d\n", iSap()); } return 0; } |
Double click to view unformatted code.