2018-team4-modules-上下界可行流

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

上下界可行流
无源汇做法：强制流满下界，流量限制变为0~mx-mn，同上建立源汇满足流量等式
对源汇做最大流，如果跑不满新加的边则说明没有可行流，否则有
有源汇做法类似， 先从汇连一条上限INF的边到源，然后用无源汇做法消掉下界，就可以知道有没有可行流
若要求最大流，则用原本的源到汇做最大流
要求最小流则从汇到源做最大流，即尽可能退流
{{{
void lim(int x,int y,int l,int r,int c=0){
    cost+=1ll*c*l;      //这是上下界费用流的费用
    deg[x]-=l,deg[y]+=l;
    if (r!=l) add(x,y,r-l,c);
}
}}}

上下界可行流

无源汇做法：强制流满下界，流量限制变为0~mx-mn，同上建立源汇满足流量等式

对源汇做最大流，如果跑不满新加的边则说明没有可行流，否则有

有源汇做法类似， 先从汇连一条上限INF的边到源，然后用无源汇做法消掉下界，就可以知道有没有可行流

若要求最大流，则用原本的源到汇做最大流

要求最小流则从汇到源做最大流，即尽可能退流

void lim(int x,int y,int l,int r,int c=0){
    cost+=1ll*c*l;      //这是上下界费用流的费用
    deg[x]-=l,deg[y]+=l;
    if (r!=l) add(x,y,r-l,c);
}