2189. 有源汇上下界最大流

标签：int 有源 sum dep w1 ans 2189 now 汇上

2189. 有源汇上下界最大流
和无源点的思路差不多，只是要跑两次图，先用虚点跑，在用实点跑。（不知道为什么我的ISAP会错）

#include <bits/stdc++.h>
using namespace std;
const int N=505;
const int M=1e6+5;

int h[N],ne[M],e[M],w[M],tot=1;
void add(int from,int to,int wi) {
    e[++tot]=to;
    w[tot]=wi;
    ne[tot]=h[from];
    h[from]=tot;
}

int n,m,s,t,S,T;
int dep[N],cur[N];

bool bfs() {
    memset(dep,0,sizeof(dep));
    memcpy(cur,h,sizeof(h));
    queue<int>q;
    dep[S]=1;
    q.push(S);
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=h[now];i;i=ne[i]) {
            int to=e[i];
            if(dep[to]==0&&w[i]>0)
                dep[to]=dep[now]+1,q.push(to);
        }
    }
    return dep[T];
}

int dfs(int now,int sum) {
    if(now==T)return sum;
    int ans=0;
    for(int i=cur[now];i&&sum;i=ne[i]) {
        cur[now]=i;
        int to=e[i];
        if(dep[to]==dep[now]+1&&w[i]>0) {
            int k=dfs(to,min(w[i],sum));
            if(k==0)dep[to]=0;
            w[i]-=k;
            w[i^1]+=k;
            sum-=k;
            ans+=k;
        }
    }
    return ans;
}
    
int dinic() {
    int ans=0;
    while(bfs())ans+=dfs(S,1e9);
    return ans;
}

int a[M],b[M];

int main() {
    cin>>n>>m>>s>>t;
    S=n+1,T=n+2;
    int sum=0;
    for(int i=1;i<=m;i++) {
        int x,y,w1,w2;
        cin>>x>>y>>w1>>w2;
        add(x,y,w2-w1);
        add(y,x,0);
        a[x]+=w1;
        a[y]-=w1;
        b[i]=w1;//最小流量
    }
    for(int i=1;i<=n;i++) {
        if(a[i]>0)add(i,T,a[i]),add(T,i,0);
        else if(a[i]<0)add(S,i,-a[i]),add(i,S,0),sum-=a[i];
    }
    add(t,s,1e9);
    add(s,t,0);
    //建立一个终点到起点的无限边
    if(dinic()!=sum)cout<<"No Solution\n";
    else {
        //先加上那条无限边，然后再跑一次图
        //并且去掉最后两条边
        int ans=w[tot];
        S=s,T=t;
        w[tot]=w[tot^1]=0;
        cout<<ans+dinic();
    }
    return 0;
}

标签：int,有源,sum,dep,w1,ans,2189,now,汇上
From： https://www.cnblogs.com/basicecho/p/16979672.html