最大流dinic算法

#include <iostream>
#include <cstring>
#include <string>
#include <queue>
using namespace std;

const int N =1000+10;
const int M = 2e4+10;

int h[N],to[M],ne[M],cap[M],flow[M],idx=0;
int dis[N];
int vi[N];

void add(int a,int b,int c){
    ne[idx]=h[a];
    cap[idx]=c;
    flow[idx]=0;
    to[idx]=b;
    h[a]=idx++;
}

int bfs(int st,int ed){
    memset(vi,0,sizeof vi);
    // memset(dis,0,sizeof dis);
    queue<int> q;
    q.push(st);
    vi[st]=1;
    dis[st]=0;
    while(q.size()){
        int t = q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i]){
            int v = to[i];
            if(vi[v])continue;
            if(cap[i]>flow[i]){
                dis[v]=dis[t]+1;
                vi[v]=1;
                q.push(v);
            }
        }
    }
    return vi[ed];
}


int dfs(int cur,int ed,int f){
    if(cur==ed||f==0)return f;
    int ff=0;
    for(int i=h[cur];~i;i=ne[i]){
        int v = to[i];
        if(dis[v]!=dis[cur]+1)continue;
        int d = dfs(v,ed,min((cap[i]-flow[i]),f));
        if(d){
            flow[i]+=d;
            flow[i^1]-=d;
            f-=d;
            ff+=d;
            if(f==0)break;
        }
    }
    return ff;
}

int mcmf(int st,int ed){
    int res=0;
    while(bfs(st,ed)){
        int d = dfs(st,ed,0x3f3f3f3f);
        res+=d;
    }
    return res;
}