网络流DINIC模板

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>                                       ///矩阵存图
#include <stack>
#include <cctype>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <climits>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define fi first
#define se second
#define ping(x,y) ((x-y)*(x-y))
#define mst(x,y) memset(x,y,sizeof(x))
#define Min(x,y) (x<y?x:y)
using namespace std;
#define gamma 0.5772156649015328606065120 //欧拉常数
#define MOD 100000007
#define inf 0x3f3f3f3f
#define N 1000010
#define maxn 10001000
typedef long long LL;
typedef pair<int,int> PII;

int n,m;
int pic[300][300],lel[300];

int bfs()
{
    mst(lel,-1);
    lel[1]=0;
    queue<int>q;
    q.push(1);
    while(!q.empty()&&lel[n]==-1)
    {
        int u=q.front();
        q.pop();
        for(int i=2; i<=n; ++i)
        {
            if(lel[i]==-1&&pic[u][i])
            {
                lel[i]=lel[u]+1;   ///等级标号
                q.push(i);
            }
        }
    }
    return lel[n]!=-1;
}

int dfs(int start,int flow)
{
    if(start==n) return flow;
    for(int i=2; i<=n; ++i)
        if(lel[start]+1==lel[i]&&pic[start][i])
        {
            int cut=dfs(i,Min(flow,pic[start][i]));
            if(cut)
            {
                pic[start][i]-=cut;
                pic[i][start]+=cut;
                return cut;
            }
        }
    return 0;
}

int dinic()
{
    int res=0,t;
    while(bfs())
        while(t=dfs(1,inf))
            res+=t;
    return res;
}

int main()
{
    int i,x,y,v;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        mst(pic,0);
        for(i=0; i<m; ++i)
        {
            scanf("%d%d%d",&x,&y,&v);
            pic[x][y]+=v;   ///可有重边
        }
        printf("%d\n",dinic());
    }
    return 0;
}