有上下界的网络流

1.无源汇的可行流

首先一个无源汇的可行流必须要满足每个点的流量平衡，我们记为\(f_{out}=f_{in}\)。

通常，网络流这限制了上界，而无法限制下界。所以对于下界，我们的处理方法就是先让所有边的流量达到下界\(d\)，然后将一条流量在\([d,u]\)的边的流量设为\(u-d\)。这样就没有下界的问题了。

显然，这么操作后的结果很可能不是一个可行流，所以我们需要继续调整。

对于一个点\(v\)，设调整后它获得的入边和出边的流量分别为\(g_{in},g_{out}\)，原始入边和出边的下界之和分别为\(d_{in},d_{out}\)。因为流量平衡，所以\(g_{in}+d_{in}=g_{out}+d_{out}\)。假设\(d_{out}>d_{in}\)，则\(g_{in}-g_{out}=d_{out}-d_{in}\)，也就是说流入的流量要大于流出的流量，反之也是一样的道理。

然后对于\(d_{out}>d_{in}\)的点，我们建立超级源连向它，流量为\(d_{out}-d_{in}\)，表示它要向外额外输出流量；反过来就建立超级汇，将\(d_{out}<d_{in}\)的点连向超级汇，表示它要额外输入流量。

原图上的边就按上面所说的方式处理。

仔细一想就会发现，超级源的所有出边的流量和与超级汇的所有入边流量和相同。如果我们跑一边SAP发现满流，则存在可行流。每条边的流量为残余网络中的流量+下界。

2.有源汇的可行流

首先有源汇与无源汇的区别在于：有源汇可行流中，源点和汇点不一定流量平衡，但是源点多余的流量=汇点的多余流量。

解决有源汇问题时我们通常将其转化为无源汇的问题，具体方法就是连一条\((T,S,\infty,0)\)的边。这样的话，汇点多余的输出就可以通过这条边进入源点。

然后我们建立超级源SS与超级汇TT，之后判断是否有可行流就用1的方法。

3.有源汇的最大/最小流

处理这类问题时我们先用2的方法做一遍。

此时的源汇之间的流量就是那条无穷边的流量，我们记为\(w\)。注意到\(w\)不一定是最大/最小流，所以我们还需做下面的事情。

最大流

因为\(S\)与\(T\)之间可能存在富余的边，导致没有得到最大流。

我们将超级源和超级汇以及与他们相连的边拆掉，然后在残余网络上在跑一次最大流。得到新的最大流与\(w\)的和就是答案。

为什么跑最大流的时候不会破坏流量平衡？

因为残余网络是流量平衡的(除了源汇点)，在跑最大流的时候每个中间节点流入的流量与流出的流量是相同的，所以依然满足流量平衡。

最小流

法1：与最大流类似。我们先得到了\(w\)之后我们尽量减少\(S\)和\(T\)之间的流量。于是我们拆了超级源和超级汇之后“反着”跑最大流，也就是拿\(T\)当源点，\(S\)当汇点跑最大流。可以这么理解：反边增加流量相当于正边减少流量。答案就是\(w\)-最大流。

法2：当然也可以不用改变图，直接反着跑最大流，答案就是\(INF\)-最大流。这里\(INF\)就是我们\((T,S,\infty,0)\)的上界。

正确性：首先我们设我们按法1得到的最大流为\(k\)，那么法2得到的最大流为\(k+(INF-w)\)。因为\((T,S,\infty,0)\)流了\(w\)，所以其反边有\(INF-w\)的流量。

答案\(=INF-(k+(INF-w))=w-k\)。与法1等价的。

4.例题(Loj)

代码：

#include
    
     #define ll long long#define N 205#define M 15005using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n,m;int S,T;int flow[N];struct load {    int to,next,flow;}s[M<<2];int h[N],cnt=1;void add(int i,int j,int flow) {    s[++cnt]=(load) {j,h[i],flow};h[i]=cnt;    s[++cnt]=(load) {i,h[j],0};h[j]=cnt;}int gap[N],dis[N];ll dfs(int v,int maxf) {    if(v==T) return maxf;    int ret=0;    for(int i=h[v];i;i=s[i].next) {        int to=s[i].to;        if(dis[to]+1==dis[v]&&s[i].flow) {            int dlt=dfs(to,min(maxf-ret,s[i].flow));            s[i].flow-=dlt;            s[i^1].flow+=dlt;            ret+=dlt;            if(ret==maxf||dis[S]==n+2) return ret;        }    }    if(!(--gap[dis[v]])) dis[S]=n+2;    gap[++dis[v]]++;    return ret;}int sap() {    gap[0]=n+2;    int ans=0;    while(dis[S]
     
      0) add(S,i,flow[i]);        else if(flow[i]<0) add(i,T,-flow[i]);    }    sap();    for(int i=h[S];i;i=s[i].next) {        if(s[i].flow) {            cout<<"NO";return 0;        }    }    cout<<"YES\n";    for(int i=1;i<=m;i++) {        cout<
      
       <<"\n";    }    return 0;}
      
     
    

代码：

#include
    
     #define ll long long#define N 505#define M 250005#define INF (int)1e8using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n,m;int S,T;int st,ed;struct load {    int to,next;    int flow,d;}s[M<<1];int h[N],cnt=1;void add(int i,int j,int d,int u) {    s[++cnt]=(load) {j,h[i],u-d,d};h[i]=cnt;    s[++cnt]=(load) {i,h[j],0,d};h[j]=cnt;}int gap[N],dis[N];int dfs(int v,int maxf) {    if(v==T) return maxf;    int ret=0;    for(int i=h[v];i;i=s[i].next) {        int to=s[i].to;        if(s[i].flow>0&&dis[to]+1==dis[v]) {            int dlt=dfs(to,min(maxf-ret,s[i].flow));            s[i].flow-=dlt;            s[i^1].flow+=dlt;            ret+=dlt;            if(dis[S]>=n+2||ret==maxf) return ret;        }    }    if(!(--gap[dis[v]])) dis[S]=n+2;    gap[++dis[v]]++;    return ret;}int sap() {    memset(dis,0,sizeof(dis));    memset(gap,0,sizeof(gap));    gap[0]=n+2;    int ans=0;    while(dis[S]
     
      0) add(S,i,0,flow[i]),sum+=flow[i];        else if(flow[i]<0) add(i,T,0,-flow[i]);    }    int now=sap();    if(now!=sum) {cout<<"please go home to sleep";return 0;}    S=st,T=ed;    int ans=0;    for(int i=h[ed];i;i=s[i].next) {        if(s[i].flow>1e7) {            ans+=s[i^1].flow;            break;        }    }    for(int i=tag;i<=cnt;i++) s[i].flow=0;    ans+=sap();    cout<
     
    

代码：

#include
    
     #define ll long long#define N 50005#define M 200005using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n,m,st,ed;int S,T;struct load {    int to,next;    ll flow;}s[M<<1];int h[N],cnt=1;void add(int i,int j,ll flow) {    s[++cnt]=(load) {j,h[i],flow};h[i]=cnt;    s[++cnt]=(load) {i,h[j],0};h[j]=cnt;}int flow[N];int dis[N],gap[N];int cur[N]; ll dfs(int v,ll maxf) {    if(v==T) return maxf;    ll ret=0;    for(int &i=cur[v];i;i=s[i].next) {        int to=s[i].to;        if(s[i].flow&&dis[to]+1==dis[v]) {            ll dlt=dfs(to,min(maxf-ret,s[i].flow));            s[i].flow-=dlt;            s[i^1].flow+=dlt;            ret+=dlt;            if(ret==maxf||dis[S]>=n+2) return ret;        }    }    if(!(--gap[dis[v]])) dis[S]=n+2;    gap[++dis[v]]++;    cur[v]=h[v];    return ret;}ll sap() {    memset(dis,0,sizeof(dis));    memset(gap,0,sizeof(gap));    gap[0]=n+2;    ll ans=0;    for(int i=0;i<=n+2;++i) cur[i]=h[i];    while(dis[S]
     
      0) add(S,i,flow[i]),sum+=flow[i];        else if(flow[i]<0) add(i,T,-flow[i]);    }    ll now=sap();        if(now!=sum) {cout<<"please go home to sleep";return 0;}        for(int i=tag;i<=cnt;i++) s[i].flow=0;    S=ed,T=st;    cout<<(1ll<<50)-sap();        return 0;}