HOJ 1532 Drainage Ditches（最大流EK算法，裸题）

最大流EK算法，裸题
本题要点：
1、EK算法的步骤：
先用 bfs，判断图中知否存在一条增光路；
存在增光路，那么每次更新这条增光路；
2、更新增光路：
pre[i] 表示增光路上，i点的前一个点的下标
incf[i], 表示起点s 到达点i的增光路上各边的最小剩余容量。
因此，增光路上的每一条边都应该减去 incf[t]

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int MaxN = 210, MaxM = 510;
const int inf = 1 << 29;
int head[MaxN], ver[MaxM], edge[MaxM], Next[MaxM], vis[MaxN];
int incf[MaxN], pre[MaxN];
int g[MaxN][MaxN];	//邻接矩阵，用于去重边
int n, m, st, ed, tot, maxflow;void add(int x, int y, int z)
{
    ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
}bool bfs()
{
    memset(vis, 0, sizeof vis);queue<int> q;q.push(st);vis[st] = 1;incf[st] = inf;		//增光路上各边的最小剩余容量while(q.size()){
    int x = q.front(); q.pop();for(int i =head[x]; i; i = Next[i]){
    if(edge[i]){
    int y = ver[i];if(vis[y])	continue;incf[y] = min(incf[x], edge[i]);pre[y] = i;	//记录前驱q.push(y), vis[y] = 1;if(y == ed)	return 1;}}}return 0;
}void update()
{
    int x = ed;while(x != st){
    int i = pre[x];edge[i] -= incf[ed];;edge[i ^ 1] += incf[ed];x = ver[i ^ 1];}maxflow += incf[ed];
}int main()
{
    int x, y, z;while(scanf("%d%d", &m, &n) != EOF){
    memset(head, 0, sizeof head);memset(Next, 0, sizeof Next);memset(g, 0, sizeof g);st = 1, ed = n, tot = 1, maxflow = 0;for(int i = 0; i < m; ++i){
    scanf("%d%d%d", &x, &y, &z);g[x][y] += z;}for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= n; ++j){
    if(g[i][j]){
    add(i, j, g[i][j]);}}}while(bfs()){
    update();}printf("%d\n", maxflow);}return 0;
}/* 5 4 1 2 40 1 4 20 2 4 20 2 3 30 3 4 10 *//* 50 */