Dinic模板（最大流最小割）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define N 5005
#define LL long long
#define MAXLL 0x3f3f3f3f3f3f3f3f
using namespace std;

struct Edge{
int to,rev;
    LL cap;
    Edge(){};
    Edge(int to,LL cap,int rev)
    {
this->to=to;
this->rev=rev;
this->cap=cap;
    }
};

int n,m;
vector<Edge> edge[N];
int level[N];
int used[N];

//向图中增加边
void addEdge(int from,int to,LL cap)
{
    edge[from].push_back(Edge(to,cap,edge[to].size()));
    edge[to].push_back(Edge(from,0,edge[from].size()-1));
}

//计算从源点出发的距离标号
void bfs(int s)
{
memset(level,-1,sizeof(level));
queue<int> q;
    level[s]=0;
    q.push(s);
while(!q.empty())
    {
int v=q.front();
        q.pop();
for(int i=0;i<edge[v].size();i++)
        {
            Edge &e=edge[v][i];
if(e.cap>0&&level[e.to]<0)
            {
                level[e.to]=level[v]+1;
                q.push(e.to);
            }
        }
    }
}

//寻找增广路
LL dfs(int v,int t,LL f)
{
if(v==t) return f;
for(int &i=used[v];i<edge[v].size();i++)
    {
        Edge &e=edge[v][i];
if(e.cap>0&&level[v]<level[e.to])
        {
            LL tmp=dfs(e.to,t,min(f,e.cap));
if(tmp>0)
            {
                e.cap-=tmp;
                edge[e.to][e.rev].cap+=tmp;
return tmp;
            }
        }
    }
return 0;
}

LL maxFlow(int s,int t)
{
    LL flow=0;
for(;;)
    {
        bfs(s);
if(level[t]<0)
return flow;
memset(used,0,sizeof(used));
        LL f;
while((f=dfs(s,t,MAXLL))>0)
            flow+=f;
    }
}