网络流

· · 个人记录

负权边的处理

最小费用最大流

考虑将 dinic 的bfs部分换成 SPFA，在没有负环的前提下求费用流。

但这玩意劣化成了EK阿。

最大权闭合子图

P3749 [六省联考2017]寿司餐厅 网络流：最小割，最大权闭合子图。 注意强选的条件和 正权sum-flow的转化即可。

强选打包：连inf边。先选正权和sum，再正权连S，负权连T，流量都是 |w|，跑最小割即可。

其实最小割模型严格强于这个。

CF103E Buying Sets 需要较强的理解。

上下界网络流

指给出每条边的上下界。流量要在这个范围内。

无源汇上下界可行流：询问是否存在一种标定每条边流量的方式，使得每条边流量满足上下界同时每一个点流量平衡。

先连下界，这是必须的。连新边，这条边的下界是0，上界是上下界的差。这意味着我们之后能够支配的流量。考虑最终平衡：按照当前的构造一定有某些点要么需要流量要么需要流出，我们要达到的目的是将所有要流出的点作为起点，需要流量的点作为汇点，按当前网络能够流平。怎么解决呢？考虑给所有起点连一个源点，终点连一个总汇点。在新的网络上跑最大流，最后看最大流是否等于要流出的流量和。

有源汇上下界可行流：只有源汇不需要流量平衡。

考虑将 t->s 连一条上界为 inf 下界为0的边。转换成无源汇上下界网络流问题。最终可行流就是这条边的流量。（具体而言，就是这条边反边的w，一般为 e[tot].w）

有源汇上下界最大流：在可行流的基础上求最大流。

先跑可行流，再在删去所有附加边的残量网络上跑 s->t 的最大流。

考虑正确性：删掉了什么附加边？在求可行流时的t->s，在求无源汇可行流时的u->T,S->v，这些都是原图没有的。残量网络剩下了啥，为啥还可能有流？考虑一开始无源汇可行的构造，本质上构造了在保证下界还可行的情况下的尽可能小流（我愿称之为扰动最小流），毕竟从可行性上这是下限（不是最小的，因为一段大流量路径却可能是平衡的）。某些边的流量仍可能被适当放大，它们被留存在了残量网络上。这时再得到的最大流补上了这些流量。

有源汇上下界最小流：这个的正确性看上面括号内容。

在残量网络中跑 t->s 的最大流（不用反边，有流意味着是之前的最大流时的反边可以反悔一部分）。可行流减去这个最大流。

最大和最小唯一的区别

Can+maxflow(s,t)
Can-maxflow(t,s)

有源汇上下界最小流板子

P4843 清理雪道

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1; char s;
    while((s=getchar())<'0'||s>'9') if(s=='-') f=-1;
    while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+(s^'0'),s=getchar();
    return x*f;
}
#define rg register int
const int inf=2100000000; 
const int N=105; 
int n,m,s,t,S,T,tot=1,cnt,inf_num,head[N];
int sum[N];//下界时每条边的流出流量 
struct node{
    int to,nxt,w;
}e[N<<7];
inline void add(int u,int v,int w){
    e[++tot].to=v,e[tot].nxt=head[u],head[u]=tot,e[tot].w=w;
    e[++tot].to=u,e[tot].nxt=head[v],head[v]=tot,e[tot].w=0;
}
int Can,lim;
int dis[N],now[N];
bool bfs(int S,int T){
    for(int i=1;i<=n+4;++i) dis[i]=inf;
    queue<int> q;
    q.push(S);
    dis[S]=0,now[S]=head[S];
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(rg i=head[x];i;i=e[i].nxt){
            int v=e[i].to;
            if(e[i].w>0&&dis[v]==inf){
                dis[v]=dis[x]+1;
                now[v]=head[v];
                q.push(v);
                if(v==T) return 1;
            }
        }
    }
    return 0;
}
int dfs(int u,int sum,int T){
    if(u==T) return sum;
    int k,res=0;
    for(rg i=now[u];i;i=e[i].nxt){
        int v=e[i].to;
        now[u]=i;
        if(e[i].w>0&&(dis[v]==dis[u]+1)){
            k=dfs(v,min(sum,e[i].w),T);
            if(k==0) dis[v]=inf;
            e[i].w-=k,e[i^1].w+=k;
            res+=k,sum-=k;
        }
    }
    return res;
}
int maxflow(int S,int T){//跑S->T的最大流 
    int ans=0;
    while(bfs(S,T)){
        ans+=dfs(S,inf,T);
    }
    return ans; 
}
int main(){
    cin>>n;
    s=n+1,t=n+2;
    for(int i=1;i<=n;++i){
        m=read();
        for(int j=1;j<=m;++j){
            int v=read();
            add(i,v,inf-1),sum[v]+=1,sum[i]-=1;
        }
    }
    n+=2;
    for(int i=1;i<=n-2;++i){
        add(s,i,inf),add(i,t,inf);
    }
    S=(T=n+1)+1;
    for(int i=1;i<=n-2;++i){
        if(sum[i]>0)add(S,i,sum[i]);
        if(sum[i]<0)add(i,T,-sum[i]);
    }
    add(t,s,inf);
    maxflow(S,T);
    Can=e[tot].w,e[tot].w=e[tot^1].w=0,cout<<Can-maxflow(t,s);
    return 0;
}

/*
此题本身为
有向无环图，可重复的最小路径覆盖问题
我们想要覆盖所有的边。
令每条边为 [1,+oo)
建超级源点和汇点 连所有点 [0,+oo) 

有源汇
上下界
最小流

1.t->s 连inf 跑可行流 
2.删掉inf边和可行流时的附加边。
3.跑 t->s的最大流

无源汇上下界可行流
建超级源点和汇点
先把每条边的下界连上，每条边剩下 r-l
如果一个点有多余流量则向汇点连，缺少流量则源点连向它
最终跑最大流 判断。

有源汇上下界可行流才可以跑出实际的流量，可行流量为 t->s inf边的使用流量 

网络最大流中某边的使用流量等于该边反边的可行流量 
*/