#include<stdio.h> #include<string.h> #define MAXN 20000 #define MAXE 300000 #define INF 1e9 int tmp, src, des, cnt;//src源点,des汇点,该代码标号均从0开始 int n, m; struct Edge { int from, to; int next, cap; }edge[MAXE]; int head[MAXN]; int gap[MAXN], dep[MAXN], cur[MAXN], stack[MAXN], top; int ISAP() { int cur_fLow, max_fLow, u, insert, i; memset(dep, 0, sizeof(dep));//代表深度 memset(gap, 0, sizeof(gap)); memcpy(cur, head, n); max_fLow = 0; u = src; top = 0; while (dep[src] < n) { if (u == des)//当当前点运动到汇点 { cur_fLow = INF; for (i = 0; i < top; ++i)//top栈顶,也就是将一条增广路径中所有的边全部压入一个栈中,然后从栈底开始,找出最小的流量,也就是该增广路径增加的流量 { if (cur_fLow > edge[stack[i]].cap) { insert = i; cur_fLow = edge[stack[i]].cap; } } for (i = 0; i < top; ++i)//更新残量网络,同时增加反向弧 { edge[stack[i]].cap -= cur_fLow; edge[stack[i] ^ 1].cap += cur_fLow; } max_fLow += cur_fLow;//最后总流量加上增加的流量 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;//GAP优化 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; if (minn > dep[edge[i].to]) { cur[u] = i; minn = dep[edge[i].to]; } } } ++gap[dep[u] = minn + 1];//更新当前点的深度 if (u != src) u = edge[stack[--top]].from;//将当前点回溯 } } return max_fLow; } void addedge(int u, int v, int f,int c = 0)//正方向连一次边,反方向再连一次边,不过反向的流量为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() //{ // while (scanf("%d%d", &m, &n) != EOF) // { // cnt = 0; // src = 0; // des = n - 1; // memset(head, -1, sizeof(head)); // while (m--) // { // int a, b, c; // scanf("%d%d%d", &a, &b, &c); // --a, --b; // addedge(a, b, c); // //addedge(b, a, c);如果是无向边的加上这句 // } // int ans = ISAP(); // printf("%d\n", ans); // } // return 0; //} int main(void) { int fn, fm; scanf("%d%d", &fn, &fm); 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.