2018-team4-modules-最大费用可行流

从 Trac 迁移的文章

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

原文章内容如下：

有源汇就一直跑到流的费用为负为止
无源汇做法：强制费用为正的边满流，建立源汇来满足流量等式，源流向缺流的点，多流的点流向汇
最后把源汇互换，跑一边最小费用最大流，即把从源流来的流量退回去
答案就是正权边费用之和减去最小费用
{{{
void push(int x,int y,int f,int c){
    if (c>0){
        deg[x]+=f,deg[y]-=f,sum+=LL(f)*c;
        add(x,y,f,c);
    } else add(y,x,f,-c);
}
LL cal(){
    for (i=1;i<n-1;i++){
        if (deg[i]>0) add(S,i,deg[i],0);
        if (deg[i]<0) add(i,T,-deg[i],0);
    }
    return sum-mincmf();
}
}}}

有源汇就一直跑到流的费用为负为止

无源汇做法：强制费用为正的边满流，建立源汇来满足流量等式，源流向缺流的点，多流的点流向汇

最后把源汇互换，跑一边最小费用最大流，即把从源流来的流量退回去

答案就是正权边费用之和减去最小费用

void push(int x,int y,int f,int c){
    if (c>0){
        deg[x]+=f,deg[y]-=f,sum+=LL(f)*c;
        add(x,y,f,c);
    } else add(y,x,f,-c);
}
LL cal(){
    for (i=1;i<n-1;i++){
        if (deg[i]>0) add(S,i,deg[i],0);
        if (deg[i]<0) add(i,T,-deg[i],0);
    }
    return sum-mincmf();
}