2018.08.20 loj#116. 有源汇有上下界最大流（模板）

传送门

貌似就是转成无源汇，然后两遍最大流搞定？

其实第二遍跑最大流是自动加上了第一次的答案。

代码：

#include<bits/stdc++.h>
#define N 100005
#define M 2000010
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
    int ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
int first[N],s,t,ss,tt,n,m,d[N],cnt=-1,m_[N];
struct Node{int v,next,c;}e[M];
inline void add(int u,int v,int c){e[++cnt].v=v,e[cnt].c=c,e[cnt].next=first[u],first[u]=cnt;}
inline bool bfs(){
    queue<int>q;
    memset(d,-1,sizeof(d));
    q.push(s),d[s]=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=first[x];~i;i=e[i].next){
            int v=e[i].v;
            if(d[v]!=-1||e[i].c<=0)continue;
            d[v]=d[x]+1;
            if(v==t)return true;
            q.push(v);
        }
    }
    return false;
}
inline int dfs(int x,int f){
    if(x==t||!f)return f;
    int flow=f;
    for(int i=first[x];~i;i=e[i].next){
        int v=e[i].v;
        if(flow&&d[v]==d[x]+1&&e[i].c>0){
            int tmp=dfs(v,min(flow,e[i].c));
            if(!tmp)d[v]=-1;
            e[i].c-=tmp,e[i^1].c+=tmp,flow-=tmp;
        }
    }
    return f-flow;
}
inline bool check(){
    for(int i=first[s];~i;i=e[i].next)if(e[i].c>0)return false;
    for(int i=first[t];~i;i=e[i].next)if(e[i^1].c>0)return false;
    return true;
}
inline int solve(){
    int ret=0;
    while(bfs())ret+=dfs(s,inf);
    return ret;
}
int main(){
    memset(first,-1,sizeof(first));
    int sum=0;
    n=read(),m=read(),ss=read(),tt=read(),s=0,t=n+1;
    for(int i=1;i<=m;++i){
        int u=read(),v=read(),down=read(),up=read();
        m_[u]-=down,m_[v]+=down,add(u,v,up-down),add(v,u,0);
    }
    for(int i=1;i<=n;++i){
        if(m_[i]>0)add(s,i,m_[i]),sum+=m_[i],add(i,s,0);
        if(m_[i]<0)add(i,t,-m_[i]),add(t,i,0);
    }
    add(tt,ss,inf),add(ss,tt,0);
    if(solve()!=sum){cout<<"please go home to sleep";return 0;}
    first[s]=first[t]=-1;
    s=ss,t=tt;
    cout<<solve();
    return 0;
}

2018.08.20 loj#116. 有源汇有上下界最大流（模板）的相关教程结束。