dinic模板

#include<stdio.h>
#include<string.h>
#define INF 0x3f3f3f3f
const int MAXN = 210;
int cap[MAXN][MAXN],f[MAXN][MAXN],level[MAXN],que[MAXN];
int n,s,t;
int min(int a,int b){return a > b ? b : a;}

int dinic_bfs(){
    memset(level,-1,sizeof(level));
    level[t] = 0;
    int q = 0,qs = 0;
    que[0] = t;
    while(qs <= q){
        for(int i = 0; i < n; i++){
            if(level[i] == -1 && cap[i][que[qs]] > f[i][que[qs]]){
                level[i] = level[que[qs]] + 1;
                que[++q] = i;
            }
        }
        qs++;
    }
    return level[s] != -1;
}

int dinic_dfs(int cur,int cp){
    if(cur == t)return cp;
    int tmp = cp,t;
    for(int i = 0; i < n && tmp; i++){
        if(level[i] + 1 == level[cur] && cap[cur][i] > f[cur][i]){
            t = dinic_dfs(i,min(cap[cur][i]-f[cur][i],tmp));
            f[cur][i] += t;
            f[i][cur] -= t;
            tmp -= t;
        }
    }
    return cp - tmp;
}

int dinic(){
    int flow = 0,tf = 0;
    while(dinic_bfs()){

        while(tf = dinic_dfs(s,INF)){
            flow += tf;
        }
    }
    return flow;
}
int main()
{
    int i,j,k,u,v,w,m;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(cap,0,sizeof(cap));
        memset(f,0,sizeof(f));
        for(i = 0;i < m;i++)
        {
            scanf("%d%d%d",&v,&u,&w);
            cap[v-1][u-1] += w;
        }
        s = 0;t = n-1;
        int ans=dinic();
        printf("%d\n",ans);
    }
}