最大流模板Dinic O(m*n^2)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1004;
const int INF = 0x3f3f3f3f;
int head[20],layer[20],tot,n;
struct Edge {
    int to,w,Next;
}edge[maxn<<1];
void add(int x,int y,int z)
{
    edge[++tot].to=y,edge[tot].w=z,edge[tot].Next=head[x],head[x]=tot;
    edge[++tot].to=x,edge[tot].w=0,edge[tot].Next=head[y],head[y]=tot;
}
bool bfs(int s,int t)
{
    for(int i=1;i<=n;i++) layer[i]=-1;
    queue<int> q;
    q.push(s); layer[s]=0;
    while(!q.empty())
    {
        int x=q.front(),y; q.pop();
        for(int i=head[x];i;i=edge[i].Next) {
            y=edge[i].to;
            if(edge[i].w&&layer[y]==-1) 
            {
                layer[y]=layer[x]+1;
                q.push(y);
                if(y==t) return true;
            }
        }
    }
    return false;
}
int Dinic(int x,int t,int flow)
{
    if(x==t) return flow;
    int rest=flow,y,k;
    for(int i=head[x];i&&rest;i=edge[i].Next) {
        y=edge[i].to;
        if(edge[i].w&&layer[y]==layer[x]+1)
        {
            k=Dinic(y,t,min(rest,edge[i].w));
            if(!k) layer[y]=-1;
            edge[i].w-=k;
            edge[i^1].w+=k;
            rest-=k;
        }
    }
    return flow-rest;
}
int main()
{
    int t,kase=0;
    scanf("%d",&t);
    while(t--)
    {
        int m,x,y,z,flow=0,maxflow=0;
        scanf("%d%d",&n,&m);
        tot=1;
        for(int i=1;i<=n;i++) head[i]=0;
        for(int i=1;i<=m;i++) { 
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
        }
        while(bfs(1,n)) while(flow=Dinic(1,n,INF))
            maxflow+=flow;
        printf("Case %d: %d\n",++kase,maxflow);
    } 
    return 0;
}