(Sky OJ) 122. 網路流 [Flow]

https://pc2.tfcis.org/sky/index.php/problem/view/122/

Dinic Flow

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

struct Dinic {
    static const int MAX_N = 306;
    struct Edge {
        int to,cap,rev;
    };
    vector<Edge> edg[MAX_N];
    #define SZ(x) ((int)(x).size())
    void add_edge(int from,int to,int cap,bool type=false) {
        edg[from].push_back({to,cap,SZ(edg[to])});
        if (!type)edg[to].push_back({from,0,SZ(edg[from])-1});
        else edg[to].push_back({from,cap,SZ(edg[from])-1});
    }
    int n,s,t,iter[MAX_N],level[MAX_N];
    void init(int _n,int _s,int _t) {
        n=_n;
        s=_s;
        t=_t;
        for (int i=0;n>=i;i++) {
            edg[i].clear();
        }
    }
    void bfs() {
        queue<int> que;
        que.push(s);
//        for (int i=0;n>=i;i++) {
//            level[i] = -1;
//        }
        memset(level,-1,sizeof(level));
        level[s]=0;
        while (!que.empty()) {
            int t=que.front();
            que.pop();
            for (Edge e:edg[t]) {
                if (e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[t] +1;
                    que.push(e.to);
                }
            }
        }
    }
    const int INF = 1e9 +7;
    int dfs(int id,int flow) {
        if (id==t) return flow;
        for (int &i=iter[id];SZ(edg[id])>i;i++) {
            Edge &e=edg[id][i];
            if (e.cap > 0 && level[e.to] == level[id] + 1) {
                int d=dfs(e.to,min(flow,e.cap));
                if (d>0) {
                    e.cap -= d;
                    edg[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    int flow() {
        int flow=0;
        while (1) {
            bfs();
            if (level[t]==-1) break;
//            for (int i=0;n>=i;i++) iter[i]=0;
            memset(iter,0,sizeof(iter));
            int ret=0;
            while ((ret=dfs(s,INF)) > 0) flow+=ret;
        }
        return flow;
    }
} Flow;

int main () {
    int n,m;
    while (scanf("%d %d",&n,&m) != EOF) {
        Flow.init(n,1,n);
        for (int i=1;m>=i;i++) {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            Flow.add_edge(a,b,c,true);
        }
        if (n!=1)printf("%d\n",Flow.flow());
        else puts("0");
    }
}