网络流

Dinic 求最大流

int dep[N],cur[N],flow[M];
bool bfs(){
    queue<int> Q;
    memset(dep,0,sizeof(int)*(V+1));
    dep[S]=1;
    Q.push(S);
    while(Q.size()){
        int u=Q.front();Q.pop();
        for(int i=frm[u];i;i=nxt[i]){
            int v=to[i];
            if(!dep[v]&&cap[i]>flow[i]){
                dep[v]=dep[u]+1;
                Q.push(v);
            }
        }
    }
    return dep[T];
}
int dfs(int u,int f){
    if(u==T||!f)return f;
    int ret=0;
    for(int &i=cur[u];i;i=nxt[i]){
        int v=to[i];
        int d;
        if(dep[v]==dep[u]+1&&(d=dfs(v,min(f-ret,cap[i]-flow[i])))){
            flow[i]+=d;
            flow[i^1]-=d;
            ret+=d;
            if(ret==f)break;
        }
    }
    return ret;
}
int dinic(){
    int maxflow=0;
    while(bfs()){
        memcpy(cur,frm,sizeof(int)*(V+1));
        maxflow+=dfs(S,INF);
    }
    return maxflow;
}

最小割

最大流最小割定理：最小割等于最大流。