关于有上下界的可行流

有上下界的可行流就是对于一个网络流，每条边有一个流量上界和流量下界，求出一个满足流量平衡条件和容量限制条件的可行流（不唯一）

先设置一个源点和汇点

每条边的容量从down~ up变为0~up-down

每条边的下界可以视为必须流过的流量，那么对于每条边的两端两个点来说就是必须流出和流入的流量，我们可以维护每个点的一个量def，流出则加上流出的量，流入则减去流入的量，则最后def则记录的是必须流入流出的差量，如果def大于0，则该点与汇点连一条流量上限为def的边，反之和源点连一条容量上限为-def的边，这样等价于保证满足与该点相连的每条边的容量限制

然后相当于跑一个最大流，如果最大流能满足所有边的容量下限，那么就有可行流，每条边的可行流就是该边的流量下限加上反向边的流量

代码（LOJ115)

#include
    
     using namespace std;int str,des,cnt=1,adj[205],nxt[70000],to[70000],cap[70000],lev[1005],low[70000],def[205],m,n;inline int read(){
        char ch;    while((ch=getchar())<'0'||ch>'9'){
    ;}    int res=ch-'0';    while((ch=getchar())>='0'&&ch<='9')    res=res*10+ch-'0';    return res;}inline void addedge(int u,int v,int p){
        nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v,cap[cnt]=p;    nxt[++cnt]=adj[v],adj[v]=cnt,to[cnt]=u,cap[cnt]=0;}inline bool bfs(){
        int u,e,v;    queue
     
       que;    memset(lev,-1,sizeof(lev));    que.push(str),lev[str]=0;    while(!que.empty())    {
            u=que.front(),que.pop();        for(int e=adj[u];e;e=nxt[e])        {
                if(cap[e]>0&&lev[v=to[e]]==-1)            {
                    lev[v]=lev[u]+1,que.push(v);                if(v==des) return true;            }        }    }    return false;}inline int dinic(const int &u,const int &flow){
        if(u==des) return flow;    int res=0,v,flw;    for(int e=adj[u];e;e=nxt[e])    {
            if(cap[e]>0&&lev[u]
      
       0) sum+=def[i],addedge(i,des,def[i]);        if(def[i]<0) addedge(str,i,-def[i]);    }    if(solve()==sum)    {
            cout<<"YES"<
      
     
    

这是无源汇点的最大流，那么有源汇点的最大流呢？

很简单

我们给源汇点之间连一条流量容量为1~INF的边

然后…

就变成了无源汇点的可行流啦

代码都懒得贴了，再连一条边就是了