#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MAXV = 20010; const int MAXE = 400000; const int INF = 0x3f3f3f3f; 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, sizeof(head)); 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 (0 == --gap[dep[u]]) break; int minn = n; for (i = cur[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, int c = 0) { 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 = c; head[v] = cnt++; } int main(void) { //FILE *fp; //freopen("C:\\Users\\Administrator\\Desktop\\test.txt", "r", stdin); int fn, fm; while (scanf("%d%d", &fn, &fm) != EOF) { memset(head, -1, sizeof head); int a, b, c; cnt = src = 0, des = fn + 1; n = des + 1; for (int i = 1; i <= fn; i++) { scanf("%d%d", &a, &b); addEdge(src, i, a); addEdge(i, des, b); } for (int i = 0; i < fm; i++) { scanf("%d%d%d", &a, &b, &c); addEdge(a, b, c, c); } printf("%d\n", iSap()); } return 0; } |
Double click to view unformatted code.