(UVA) 820 - Internet Bandwidth [Dinic flow]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=761

flow 模板XD

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

const int MAX_N = 106;
const int INF = 1e9 + 7;

struct edge {
    int to,cap,rev;
};

vector<edge> G[MAX_N];
int level[MAX_N];
int iter[MAX_N];

void add_edge(int from,int to,int cap) {
    G[from].push_back((edge){to,cap,G[to].size()});
    G[to].push_back((edge){from,0,G[from].size()-1});
}

void BFS(int s) {
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int v=que.front();
        que.pop();
        int len=G[v].size();
        for (int i=0;len>i;i++) {
            edge &e=G[v][i];
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int v,int t,int f) {
    //cout<<"v  = " << v <<" , t = " <<t <<" , f = "<<f<<endl;
    if (v==t) return f;
    int len=G[v].size();
    for (int &i=iter[v]; i<len;i++) {
        edge &e=G[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d=dfs(e.to,t,min(f,e.cap));
            if (d>0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                //cout<<"innnnn\n";
                return d;
            }
        }
    }
    return 0;
}

int Dinic(int s,int t) {
    int flow = 0;
    for (;;) {
        BFS(s);
        if (level[t] < 0) return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while ((f = dfs(s,t,INF)) > 0) {
            //cout<<"get f = "<<f<<endl;
            flow += f;
        }
    }
}

int main () {
    int n;
    int cases=0;
    while (scanf("%d",&n) != EOF) {
        if (n==0) return 0;
        int s,t,m;
        scanf("%d %d %d",&s,&t,&m);
        for (int x=0;n>=x;x++) {
            G[x].clear();
        }
        for (int x=1;m>=x;x++) {
            int i,j,k;
            scanf("%d %d %d",&i,&j,&k);
            add_edge(i,j,k);
            add_edge(j,i,k);
        }
        printf("Network %d\n",++cases);
        printf("The bandwidth is %d.\n\n",Dinic(s,t));
    }
}