网络流

详细的解析

解决vector问题

最小割=最大流

技巧：连+inf的边

Dinic code

int n,m,s,t;
struct edge{
    int v,w,r;
};
vector<edge>G[10001];
bool vis[10001];
int d[10001],p[10001];
bool bfs(){
    memset(d,-1,sizeof(d));
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(s);
    vis[s]=true;
    d[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(auto i:G[u]){
            int v=i.v,w=i.w;
            if(!vis[v]&&w&&d[v]==-1){
                d[v]=d[u]+1;
                vis[v]=true;
                q.push(v);
            }
        }
    }
    if(d[t]==-1)return false;
    else return true;
}
int dfs(int u,int lim){
    if(u==t)return lim;
    for(int i=p[u];i<G[u].size();i++){
        p[u]=i;
        int v=G[u][i].v,w=G[u][i].w,r=G[u][i].r;
        if(d[v]==d[u]+1&&w){
            int tmp=dfs(v,min(lim,w));
            if(tmp){
                G[u][i].w-=tmp;
                G[v][G[u][i].r].w+=tmp;
                return tmp;
            }
            else{
                d[v]=-1;
            }
        }
    }
    return 0;
}
int dinic(){
    int ans=0;
    while(bfs()){
        memset(p,0,sizeof(p));
        while(true){
            int now=dfs(s,0x3f3f3f3f);
            if(now==0)break;
            ans+=now;
        }
    }
    return ans;
}

vector 加边

void add(int u,int v,int w){
    int ru=G[v].size();
    int rv=G[u].size();
    G[u].push_back({v,w,ru});
    G[v].push_back({u,0,rv});
}