有源汇上下界最大流/最小流

最大流

#ifdef ONLINE_JUDGE 
#else 
#define Qiu_Cheng 
#endif 
#include <bits/stdc++.h> 
#define int long long 
using namespace std; 
// typedef long long ll; 
const int N=1e5+5,mod=1e9+7,inf=INT_MAX; 
// const int mod1=469762049,mod2=998244353,mod3=1004535809;
// const int G=3,Gi=332748118; 
// const int M=mod1*mod2;
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-'){f=-1;}c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c-'0');c=getchar();}
    return x*f;
}
inline void write(int x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int n,m;
int pos[N],dep[N];
int l[N],r[N],cha[N];
struct node{int to,c,lp;};
vector<node>g[N];
void add(int from,int to,int c)
{
    g[from].push_back((node){to,c,(int)g[to].size()});
    g[to].push_back((node){from,0,(int)g[from].size()-1});
}
void fc(int s)
{
    memset(dep,-1,sizeof(dep));
    dep[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(auto v:g[u])
        {
            if(v.c>0&&dep[v.to]<0)
            {
                dep[v.to]=dep[u]+1;
                q.push(v.to);
            }
        }
    }
}
int dfs(int u,int t,int f)
{
    if(u==t||!f) return f;
    int ans=0;
    for(int &i=pos[u];i<g[u].size();i++)
    {
        auto &x=g[u][i];
        if(x.c>0&&dep[x.to]==dep[u]+1)
        {
            int frz=dfs(x.to,t,min(f,x.c));
            if(frz>0)
            {
                x.c-=frz;g[x.to][x.lp].c+=frz;
                f-=frz;ans+=frz;
                if(!f)break;
            }
        }
    }
    return ans;
}
int max_flow=0;
int dinic(int s,int t)
{
    int flow=0;
    while(1)
    {
        fc(s);
        if(dep[t]==-1) return flow;
        memset(pos,0,sizeof(pos));
        flow+=dfs(s,t,inf);
    }
}
int ss,tt,S,T;
inline void solve()
{
    cin>>n>>m>>ss>>tt;
    S=0,T=n+2;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y>>l[i]>>r[i];
        add(x,y,r[i]-l[i]);
        cha[x]-=l[i],cha[y]+=l[i];
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(cha[i]>0) add(S,i,cha[i]),cnt+=cha[i];
        else if(cha[i]<0) add(i,T,-cha[i]);
    }
    int zky=g[ss].size();
    add(tt,ss,mod);
    if(dinic(S,T)!=cnt){cout<<"No Solution"<<endl;return;}
    else
    {
        max_flow+=g[ss][zky].c;
        g[ss][g[ss].size()-1].c=0;
        g[tt][g[tt].size()-1].c=0;
        // g[s].erase(g[s].begin()+g[s].size(),g[s].begin()+g[s].size()+1);
        // g[t].erase(g[t].begin()+g[t].size(),g[t].begin()+g[t].size()+1);
        max_flow+=dinic(ss,tt);
        cout<<max_flow<<endl;
    }
}
signed main() 
{ 
#ifdef Qiu_Cheng 
    freopen("1.in","r",stdin); 
    freopen("1.out","w",stdout); 
#endif 
    // ios::sync_with_stdio(false); 
    // cin.tie(0); cout.tie(0); 
    // int QwQ; 
    // cin>>QwQ; 
    // while(QwQ--)solve(); 
    solve(); 
    return 0; 
}
//12 825076913 0 173167432
//  6666   66666  666666 
// 6    6  6   6      6 
// 6    6  6666      6 
// 6    6  6  6    6 
//  6666   6   6  6666666

//g++ -O2 -std=c++14 -Wall "-Wl,--stack= 536870912 " cao.cpp -o cao.exe

最小流

#ifdef ONLINE_JUDGE 
#else 
#define Qiu_Cheng 
#endif 
#include <bits/stdc++.h> 
#define int long long 
using namespace std; 
// typedef long long ll; 
const int N=5e5+5,mod=1e9+7,inf=1e18; 
// const int mod1=469762049,mod2=998244353,mod3=1004535809;
// const int G=3,Gi=332748118; 
// const int M=mod1*mod2;
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-'){f=-1;}c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c-'0');c=getchar();}
    return x*f;
}
inline void write(int x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int n,m;
int pos[N],dep[N];
int l[N],r[N],cha[N];
struct node{int to,c,lp;};
vector<node>g[N];
void add(int from,int to,int c)
{
    g[from].push_back((node){to,c,(int)g[to].size()});
    g[to].push_back((node){from,0,(int)g[from].size()-1});
}
void fc(int s)
{
    memset(dep,-1,sizeof(dep));
    dep[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(auto v:g[u])
        {
            if(v.c>0&&dep[v.to]<0)
            {
                dep[v.to]=dep[u]+1;
                q.push(v.to);
            }
        }
    }
}
int dfs(int u,int t,int f)
{
    if(u==t||!f) return f;
    int ans=0;
    for(int &i=pos[u];i<g[u].size();i++)
    {
        auto &x=g[u][i];
        if(x.c>0&&dep[x.to]==dep[u]+1)
        {
            int frz=dfs(x.to,t,min(f,x.c));
            if(frz>0)
            {
                x.c-=frz;g[x.to][x.lp].c+=frz;
                f-=frz;ans+=frz;
                if(!f)break;
            }
        }
    }
    return ans;
}
int max_flow=0;
int dinic(int s,int t)
{
    int flow=0;
    while(1)
    {
        fc(s);
        if(dep[t]==-1) return flow;
        memset(pos,0,sizeof(pos));
        flow+=dfs(s,t,inf);
    }
}
int ss,tt,S,T;
inline void solve()
{
    cin>>n>>m>>ss>>tt;
    S=0,T=n+2;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y>>l[i]>>r[i];
        add(x,y,r[i]-l[i]);
        cha[x]-=l[i],cha[y]+=l[i];
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(cha[i]>0) add(S,i,cha[i]),cnt+=cha[i];
        else if(cha[i]<0) add(i,T,-cha[i]);
    }
    int zky=g[ss].size();
    add(tt,ss,inf);
    if(dinic(S,T)!=cnt){cout<<"No Solution"<<endl;return;}
    else
    {
        max_flow+=g[ss][zky].c;
        g[ss][g[ss].size()-1].c=0;
        g[tt][g[tt].size()-1].c=0;
        // g[s].erase(g[s].begin()+g[s].size(),g[s].begin()+g[s].size()+1);
        // g[t].erase(g[t].begin()+g[t].size(),g[t].begin()+g[t].size()+1);
        max_flow-=dinic(tt,ss);
        cout<<max_flow<<endl;
    }
}
signed main() 
{ 
#ifdef Qiu_Cheng 
    freopen("1.in","r",stdin); 
    freopen("1.out","w",stdout); 
#endif 
    // ios::sync_with_stdio(false); 
    // cin.tie(0); cout.tie(0); 
    // int QwQ; 
    // cin>>QwQ; 
    // while(QwQ--)solve(); 
    solve(); 
    return 0; 
}
//12 825076913 0 173167432
//  6666   66666  666666 
// 6    6  6   6      6 
// 6    6  6666      6 
// 6    6  6  6    6 
//  6666   6   6  6666666

//g++ -O2 -std=c++14 -Wall "-Wl,--stack= 536870912 " cao.cpp -o cao.exe