网络最大流 Dinic

· · 个人记录

非最小费用最大流

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,s,t,head[205],tot=1;
int _head[205];
struct edge{int nex,to,w;} e[10005];
void ADD(int u,int v,int w){e[++tot].nex=head[u],e[tot].to=v,e[tot].w=w;head[u]=tot;}
void add(int u,int v,int w){ADD(u,v,w),ADD(v,u,0);}
queue<int>q;
int de[205];
bool bfs(){
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;i++) de[i]=0,_head[i]=head[i];
    q.push(s);
    de[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nex){
            int v=e[i].to,w=e[i].w;
            if(w>0&&!de[v]){
                de[v]=de[u]+1;
                q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
int dfs(int u,int now){
    if(u==t) return now;
    int sum=0;
    for(int i=_head[u];i&&now>0;i=e[i].nex){
        _head[u]=i;
        int v=e[i].to,w=e[i].w;
        if(w>0&&de[v]==de[u]+1){
            int tmp=dfs(v,min(now,w));
            if(!tmp) de[v]=0;
            e[i].w-=tmp,e[i^1].w+=tmp;
            sum+=tmp,now-=tmp;
        }
    }
    return sum;
}
int dinic(){
    int res=0;
    while(bfs()){
        res+=dfs(s,INT_MAX);
    }
    return res;
}
signed main(){
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    for(int i=1,u,v,w;i<=m;i++) scanf("%lld%lld%lld",&u,&v,&w),add(u,v,w);
    printf("%lld\n",dinic());
    return 0;
}