XCPC Notes

Appearance

发布时间：2024-02-25

概念 ​

img

  • 残流网络
    • c′(u,v)=c(u,v)−f(u,v)c'(u,v)=c(u,v)-f(u,v)
    • c(v,u)=f(u,v)c(v,u)=f(u,v)(可以退回去)
  • ∣f+f′∣=∣f∣+∣f′∣|f+f'|=|f|+|f'|
  • 增广路径：沿着大于0的边能走到终点的路径
  • 割的定义
    • 将点集分成两部分：源点集S和汇点集T，称作割源点集S和汇点集T ，称作割
    • 割的容量：c(S,T)=∑u属于S∑v属于Tc(u,v)c(S,T)= \sum_{u属于S} \sum_{v属于T} c(u,v)
  • 可行流f和割容量c(S,T),满足∣f∣<=c(S,T)即最大流等于最小割可行流f和割容量c(S,T),满足|f|<=c(S,T) 即最大流等于最小割

Edmonds-Karps算法O(nm2)(能处理103−104规模的网络)O(nm^2)(能处理10^3-10^4规模的网络) ​

  1. bfs找增广路
  2. 更新残留网络(正向减去f，反向加f，总流加f)
  3. 用链式前向星存图，连续存正反边，则异或即为反边

模板 ​

cpp
const int N=210,M=10010;
int n,m,S,T;//S为源点,T为汇点
int e[M],h[N],ne[M],idx;//链式前向星
int f[M],d[N],pre[N];//f存流量，d存增广路的最小值，pre求前驱路径的idx
void add(int a,int b,int c){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;//反向流量初始为0
}   
bool bfs(){
    queue<int> q;
    memset(vis,0,sizeof vis);
    q.push(S);
    vis[S]=1;
    d[S]=INF;
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(!vis[v]&&f[i]){
                vis[v]=1;
                d[v]=min(d[u],f[i]);
                pre[v]=i;
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int EK(){
    int r=0;
    while(bfs()){
        r+=d[T];
        for(int i=T;i!=S;i=e[pre[i]^1]){
            f[pre[i]]-=d[T],f[pre[i]^1]+=d[T];
        }
    }
    return r;
}
void solve(){
    cin>>n>>m>>S>>T;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
    cout<<EK();
}

Dinic算法 O(n2m)(能处理104−105规模的网络)O(n^2m)(能处理10^4-10^5规模的网络) ​

  1. 对EK算法的优化，dfs将所有增广路同时遍历
  2. 因为可能有环，因此需要bfs预处理一遍深度，分层遍历
  3. 对于一个节点x，当它在DFS中走到了第i条弧时，前i−1条弧到汇点的流一定已经被流满而没有可行的路线了那么当下一次再访问x节点时，前i−1条就没有任何意义了
cpp
const int N=210,M=10010;
int n,m,S,T;//S为源点,T为汇点
int e[M],h[N],ne[M],idx;//链式前向星
int f[M],d[N],cur[N];//f存流量，d存层数，cur为弧优化，表示当前从哪条节点开始搜
void add(int a,int b,int c){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;//反向流量初始为0
}   
bool bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    q.push(S);
    d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                d[v]=d[u]+1;
                cur[v]=h[v];//一开始所有边都可以搜
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){//深搜，limit表示从源点流向u的最多能流的流，flow表示已经流向汇点多少流
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){//flow<limit优化很重要，否则易tle
        int v=e[i];
        cur[u]=i;//弧优化更新
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;//如果到达不了T,标记下次就不会走到
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }   
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())
        while(flow=find(S,INF))r+=flow;
    return r;
}
void solve(){
    cin>>n>>m>>S>>T;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
    cout<<dinic();
}

Dinic封装版 ​

cpp
struct MaxFlow{
    vector<int> e,h,ne;//链式前向星
    int n,idx,S,T;//S为源点,T为汇点
    vector<int> f,d,cur;//f存流量，d存层数，cur为弧优化，表示当前从哪条节点开始搜
    MaxFlow(){}
    MaxFlow(int n){
        init(n);
    }
    void init(int n,int S=0,int T=0){
        h.assign(n+1,-1);
        d.assign(n+1,0);
        cur.assign(n+1,0);
        e.clear();
        ne.clear();
        f.clear();
        idx=0;
        this->n=n;
        this->S=S;
        this->T=T==0?n:T;
    }
    void newEdge(int x=2){
        for(int i=0;i<x;i++){
            e.emplace_back();
            ne.emplace_back();
            f.emplace_back();
        }
    }
    void addEdge(int a,int b,int c){
        newEdge();
        e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
        e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;//反向流量初始为0
    }
    bool bfs(){
        queue<int> q;
        d.assign(n+1,-1);
        q.push(S);
        d[S]=0,cur[S]=h[S];
        while(!q.empty()){
            auto u=q.front();
            q.pop();
            for(int i=h[u];~i;i=ne[i]){
                int v=e[i];
                if(d[v]==-1&&f[i]){
                    d[v]=d[u]+1;
                    cur[v]=h[v];//一开始所有边都可以搜
                    if(v==T)return true;
                    q.push(v);
                }
            }
        }
        return false;
    }
    int find(int u,int limit){//深搜，limit表示从源点流向u的最多能流的流，flow表示已经流向汇点多少流
        if(u==T)return limit;
        int flow=0;
        for(int i=cur[u];~i&&flow<limit;i=ne[i]){//flow<limit优化很重要，否则易tle
            int v=e[i];
            cur[u]=i;//弧优化更新
            if(d[v]==d[u]+1&&f[i]){
                int t=find(v,min(f[i],limit-flow));
                if(!t)d[v]=-1;//如果到达不了T,标记下次就不会走到
                f[i]-=t,f[i^1]+=t,flow+=t;
            }
        }   
        return flow;
    }
    int dinic(){
        int r=0,flow;
        while(bfs())
            while(flow=find(S,INF))r+=flow;
        return r;
    }
};

网络流应用 ​

可行流<=>可行解可行流<=>可行解

  • 关键：建图

二分图匹配 O(mn)O(m \sqrt n) ​

  • 将源点S与左边点连一条边，右边点与汇点T连一条边，所有边的容量均为1
  • 证明：显然满足容量限制和流量守恒
    • 左边点如果被选，流入容量为1，那么流出容量也只能是1即只能连一条边到右边点；右边点同理
  • 最大流=最大二分图匹配

P2756 飞行员配对方案问题(二分图模板) ​

cpp
const int N=210,M=10010;
int n,m,S,T;
int h[N],e[M],ne[M],f[M],idx;
int d[N],cur[N];
void add(int a,int b,int c){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs(){
    queue<int> q;
    q.push(S);
    memset(d,-1,sizeof d);
    d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                cur[v]=h[v];
                d[v]=d[u]+1;
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        int v=e[i];
        cur[u]=i;
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())while(flow=find(S,INF))r+=flow;
    return r;
}
void solve(){
    memset(h,-1,sizeof h);
    cin>>m>>n;
    S=0,T=n+1;
    for(int i=1;i<=m;i++)add(S,i,1);
    for(int i=m+1;i<=n;i++)add(i,T,1);
    int u,v;
    while(cin>>u>>v,u!=-1)add(u,v,1);
    cout<<dinic()<<"\n";
    for(int i=0;i<idx;i+=2){
        if(e[i]>m&&e[i]<=n&&!f[i]){
            cout<<e[i^1]<<" "<<e[i]<<"\n";
        }
    }
}

P3254圆桌问题(类二分图匹配+最大流) ​

题意：
m个不同单位，派出r_i个代表，在n个圆桌聚餐，不希望看到同一单位在同一圆桌聚餐，求是否有方案数
圆桌不一定坐满 思路：

  • 网络流建图，源点向单位建边，容量为r_i
  • 圆桌向汇点建边，容量为c_i
  • 单位对每个圆桌建边，容量为1
  • 则每个单位流入r_i，单位向一个圆桌只能流向一个人(满足题意)
  • 判断满流==人数
  • 方案数枚举：
    • v为圆桌点就输出
cpp
const int N=500,M=100010;
int n,m,S,T;
int h[N],e[M],ne[M],f[M],idx;
int d[N],cur[N];
void add(int a,int b,int c){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    d[S]=0,cur[S]=h[S];
    q.push(S);
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                d[v]=d[u]+1;
                cur[v]=h[v];
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int v=e[i];
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())while(flow=find(S,INF))r+=flow;
    return r;
}
void solve(){
    memset(h,-1,sizeof h);
    cin>>m>>n;
    S=0,T=m+n+1;
    int tot=0;
    for(int i=1;i<=m;i++){
        int c;
        cin>>c;
        tot+=c;
        add(S,i,c);
    }
    for(int i=1;i<=n;i++){
        int c;
        cin>>c;
        add(m+i,T,c);
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++)add(i,m+j,1);
    }
    if(dinic()!=tot){
        cout<<0;
        return;
    }
    cout<<1<<"\n";
    for(int i=1;i<=m;i++){
        for(int j=h[i];~j;j=ne[j]){
            if(e[j]>m&&e[j]<=n+m&&!f[j]){
                cout<<e[j]-m<<" ";
            }
        }
        cout<<"\n";
    }
}

无源汇上下界可行流 ​

n个点，m条边有上下界满足流量守恒的可行方案

  • 核心(G,f)−>(G′,f′)核心 (G,f)->(G',f')
  • cL(u,v)<=f(u,v)<=cH(u,v)转化成0<=f(u,v)−cL(u,v)<=cH(u,v)−cL(u,v)c_L(u,v)<=f(u,v)<=c_H(u,v) 转化成0<=f(u,v)-c_L(u,v)<=c_H(u,v)-c_L(u,v)
  • cin为少进的流量，cout为少出的流量c_{in}为少进的流量，c_{out}为少出的流量
    • 源图流量守恒
    • cin>cout,即少进了cin−cout的流量，让源点S连一条边补上c_{in}>c_{out} ,即少进了c_{in}-c_{out}的流量，让源点S连一条边补上
    • cin<cout,向汇点连边c_{in}<c_{out},向汇点连边
  • 看方案是否有只需看是否满流
cpp
const int N=500,M=100010;
int n,m,S,T;
int h[N],e[M],f[M],l[M],ne[M],idx;
int d[N],cur[N],A[N];//A[i]表示i的少入还是少出
void add(int a,int b,int c,int d){
    e[idx]=b,f[idx]=d-c,l[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    q.push(S);
    d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                d[v]=d[u]+1;
                cur[v]=h[v];
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        int v=e[i];
        cur[u]=i;
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())while(flow=find(S,INF))r+=flow;
    return r;
}
void solve(){
    cin>>n>>m;
    S=0,T=n+1;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        add(a,b,c,d);
        A[a]-=c,A[b]+=c;
    }
    int tot=0;
    for(int i=1;i<=n;i++){
        if(A[i]>0)add(S,i,0,A[i]),tot+=A[i];
        else add(i,T,0,-A[i]);
    }
    if(dinic()!=tot){
        cout<<"NO\n";
        return;
    }
    cout<<"YES\n";
    for(int i=0;i<2*m;i+=2){
        cout<<f[i^1]+l[i]<<"\n";//当前边满流等于残余网络的反向边流量
    }
}

有源汇上下界最大流 ​

  • 源网络s和t不满足流量守恒,将t连一条+∞的边到s,就变成无源汇上下界可行流，建新图源网络s和t不满足流量守恒,将t连一条+∞的边到s,就变成无源汇上下界可行流，建新图
  • 则对新图的s(原网络的源点)求到t(原网络的汇点)求增广路，没有则表示源网络最大流则对新图的s(原网络的源点)求到t(原网络的汇点)求增广路，没有则表示源网络最大流
    • 证明：f<=>f′(s,t)f <=> f'(s,t)
    • 源网络的f对应新网络的满流f′源网络的f对应新网络的满流f'
      • ∣f′+f′(s,t)∣由于f′已满流，S不会有多余的流量流向s，剩余流量也进不去T，因此仍然是个满流即对应源网络的一个可行流|f'+f'(s,t)| 由于f'已满流，S不会有多余的流量流向s，剩余流量也进不去T，因此仍然是个满流即对应源网络的一个可行流
      • 假设有一个f对应新网络的f′,另有一个新网络的流f0′和f0′(s,t)则∣f′−f0′∣,满流减满流就只剩下除S,T的点可以考虑,对应f0′(s,t)假设有一个f对应新网络的f',另有一个新网络的流f_0'和f'_0(s,t) 则|f'-f'_0|,满流减满流就只剩下除S ,T的点可以考虑,对应f'_0(s,t)
    • 因此f<=>f′(s,t)因此f<=>f'(s,t)
    • 对于一个可行流f，新图存在一个满流f′与之对应，f′是一个定值，f′对应的s−>t的流量记为f0′(s,t)也是定值，要使f(s,t)=∣f0′(s,t)+f增(s,t)∣最大就要增广(s,t)对于一个可行流f，新图存在一个满流f'与之对应，f'是一个定值，f'对应的s->t的流量记为f'_0(s,t)也是定值，要使f(s,t)=|f'_0(s,t)+f_增(s,t)|最大就要增广(s,t)
  • 完整过程：
    1. t->s连边
    2. 无源上下界做法求最大流
    3. 删边t->s
    4. 残留网络求s->t最大流
    5. 若求的是最小流，则求t->s的最大流
    6. 最大流就是满流时t−>s(中间节点流量守恒，等于s−>t)的流量+增广流量最大流就是满流时t->s(中间节点流量守恒，等于s->t)的流量+增广流量
cpp
int n,m,S,T,s,t;
int h[N],e[M],f[M],ne[M],idx;
int d[N],cur[N],A[N];
void add(int a,int b,int c,int d){
    e[idx]=b,f[idx]=d-c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    d[S]=0,cur[S]=h[S];
    q.push(S);
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                d[v]=d[u]+1;
                cur[v]=h[v];
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int v=e[i];
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())while(flow=find(S,INF))r+=flow;
    return r;
}
void solve(){
    cin>>n>>m>>s>>t;
    memset(h,-1,sizeof h);
    S=0,T=n+1;
    while(m--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        add(a,b,c,d);
        A[a]-=c,A[b]+=c;
    }
    int tot=0;
    for(int i=1;i<=n;i++){
        if(A[i]>0)add(S,i,0,A[i]),tot+=A[i];
        else add(i,T,0,-A[i]);
    }
    add(t,s,0,INF);
    if(dinic()!=tot){
        cout<<"please go home to sleep\n";
        return;
    }
    int res=f[idx-1];//t->s的流量
    S=s,T=t;
    f[idx-2]=f[idx-1]=0;//流量为0，删边
    cout<<res+dinic()<<"\n";
}

有源汇上下界最小流 ​

与有源汇上下界最大流类似，只不过求的是反向增广流，最小流=原可行流-反向增广流

cpp
const int N=50010,M=(N+125003)*2;
int n,m,S,T,s,t;
int h[N],e[M],f[M],ne[M],idx;
int d[N],cur[N],A[N];
void add(int a,int b,int c,int d){
    e[idx]=b,f[idx]=d-c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    d[S]=0,cur[S]=h[S];
    q.push(S);
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                d[v]=d[u]+1;
                cur[v]=h[v];
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int v=e[i];
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())while(flow=find(S,INF))r+=flow;
    return r;
}
void solve(){
    cin>>n>>m>>s>>t;
    memset(h,-1,sizeof h);
    S=0,T=n+1;
    while(m--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        add(a,b,c,d);
        A[a]-=c,A[b]+=c;
    }
    int tot=0;
    for(int i=1;i<=n;i++){
        if(A[i]>0)add(S,i,0,A[i]),tot+=A[i];
        else add(i,T,0,-A[i]);
    }
    add(t,s,0,INF);
    if(dinic()!=tot){
        cout<<"please go home to sleep\n";
        return;
    }
    int res=f[idx-1];//t->s的流量
    S=t,T=s;
    f[idx-2]=f[idx-1]=0;//流量为0，删边
    cout<<res-dinic()<<"\n";
}

多源汇最大流 ​

建一个虚拟源点S和汇点T，S向原源点连∞边，汇点向T连∞边，跑dinic即可

最大流之关键边 ​

在流网络中，只能改变一条边的容量，使最大流增加 关键边必定是满流的 在Gf中存在S−>u且v−>T的>0的路径在G_f中存在S->u且v->T的>0的路径

模板POJ3204 Ikki's Story I - Road Reconstruction ​

cpp
int n,m,S,T;
int h[N],e[M],f[M],ne[M],idx;
int d[N],cur[N];
bool vis_s[N],vis_t[N];
void add(int a,int b,int c){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    d[S]=0,cur[S]=h[S];
    q.push(S);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                d[v]=d[u]+1;
                cur[v]=h[v];
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int v=e[i];
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())while(flow=find(S,INF))r+=flow;
    return r;
}
void dfs(int u,bool st[],int t){
    st[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int j=i^t,v=e[i];//寻找路径，如果是从T开始找,那么应该判断反向边是否满流
        if(f[j]&&!st[v])dfs(v,st,t);
    }
}
void solve(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    S=0,T=n-1;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    dinic();
    dfs(S,vis_s,0);
    dfs(T,vis_t,1);
    int res=0;
    for(int i=0;i<2*m;i+=2){
        if(!f[i]&&vis_s[e[i^1]]&&vis_t[e[i]]){
            res++;
        }
    }
    cout<<res<<"\n";
}

最大流判定 ​

P1674 [USACO05FEB] Secret Milking Machine G(秘密挤奶机，网络流+二分) ​

题意：
n个点,m条边,每条边(有长度)只能走一次,问从1-n能走t次的情况下，最长路最短 思路： 二分答案，将大于mid的边删掉，则题目转化为：

  • 给定一张流网络，最大流是否大于等于t
cpp
int n,m,S,T,t;
int h[N],e[M],f[M],ne[M],w[M],idx;
int d[N],cur[N];
void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,w[idx]=c,ne[idx]=h[b],h[b]=idx++;
}
bool bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    d[S]=0,cur[S]=h[S];
    q.push(S);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                d[v]=d[u]+1;
                cur[v]=h[v];
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int v=e[i];
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())while(flow=find(S,INF))r+=flow;
    return r;
}
bool check(int x){
    for(int i=0;i<idx;i++){
        if(w[i]>x)f[i]=0;
        else f[i]=1;
    }
    return dinic()>=t;
}
void solve(){
    cin>>n>>m>>t;
    memset(h,-1,sizeof h);
    S=1,T=n;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    int l=1,r=1e6;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l<<"\n";
}

P2754 [CTSC1999] 家园 / 星际转移问题(分层图建图) ​

  • 题意
    • 有n个空间站,m搜太空船,地球编号0,月球为-1,太空船将周期性地停靠太空站,每转移一次耗费1个时间,问转移所有人的时间
  • 思路
    • 并查集判断是否能从地球到月球
    • 网络流只与流量有关而与距离无关，要使二者产生关联应该建立分层图，每一天的每个太空站为一层，如下图所示(飞船相当于边)
      img
    • 第0天如果有飞船，则与S连容量为hi(飞船限载人数)的边第0天如果有飞船，则与S连容量为h_i(飞船限载人数)的边
    • 所有天数的n+1的点向T连+∞的边所有天数的n+1的点向T连+∞的边
    • 如果飞船能到下一个空间站，则向下一天的下一个站连边，容量为hi如果飞船能到下一个空间站，则向下一天的下一个站连边，容量为h_i
    • 飞船也可以停留一晚，向下一天的同一点连+∞的边飞船也可以停留一晚，向下一天的同一点连+∞的边
    • 可以从0开始枚举天数，在增广路增加点继续增广
cpp
int h[N],e[M],ne[M],f[M],idx;
int d[N],cur[N];
int n,m,k,S,T;
void add(int a,int b,int c){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    q.push(S);
    d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                d[v]=d[u]+1;
                cur[v]=h[v];
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i;i=ne[i]){
        cur[u]=i;
        int v=e[i];
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())while(flow=find(S,INF))r+=flow;
    return r;
}
struct Ship{
    int h,n;
    int id[30];
} ship[30];
int par[30];
int find(int x){
    return par[x]==x?x:par[x]=find(par[x]);
}
int get(int day,int x){
    return day*(n+2)+x;
}
void solve(){
    cin>>n>>m>>k;
    S=N-1,T=N-2;
    for(int i=0;i<=n+1;i++)par[i]=i;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        ship[i]={a,b};
        for(int j=0;j<b;j++){
            int id;
            cin>>id;
            if(id==-1)id=n+1;
            ship[i].id[j]=id;
            if(j){
                int x=ship[i].id[j-1];
                int fx=find(x),fy=find(id);
                if(fx!=fy)par[fx]=fy;
            }
        }
    }
    memset(h,-1,sizeof h);
    if(find(0)!=find(n+1)){
        cout<<"0\n";
        return;
    }
    add(S,get(0,0),k);
    add(get(0,n+1),T,INF);
    int day=1,res=0;
    while(true){
        add(get(day,n+1),T,INF);
        for(int i=0;i<=n+1;i++){
            add(get(day-1,i),get(day,i),INF);
        }
        for(int i=0;i<m;i++){
            auto [h,b,c]=ship[i];
            int x=c[(day-1)%b],y=c[day%b];
            add(get(day-1,x),get(day,y),h);
        }
        res+=dinic();
        if(res>=k)break;
        day++;
    }
    cout<<day<<"\n";
}

最大流拆点 ​

P2891 [USACO07OPEN] Dining G ​

有食物饮料奶牛三种点，奶牛只吃一种食物和饮料(有些喜欢有些不喜欢，不喜欢则不连边),食物饮料只能用一次,问最多有几头牛能吃到食物喝饮料

  • 类比二分图正常连边的话会有问题
    • n(n>=2)种食物流进奶牛，n条边流向饮料，这是满足可行流的，但是不满足题意
    • 将奶牛拆分成两个点，每次只允许一种食物通过奶牛即可
      img
cpp
const int N=410,M=41000;
int h[N],e[M],ne[M],f[M],idx;
int d[N],cur[N];
int n,F,D,S,T;
void add(int a,int b,int c){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    q.push(S);
    d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                d[v]=d[u]+1;
                cur[v]=h[v];
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int v=e[i];
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())while(flow=find(S,INF))r+=flow;
    return r;
}
void solve(){
    cin>>n>>F>>D;
    S=0,T=2*n+F+D+1;
    memset(h,-1,sizeof h);
    for(int i=1;i<=F;i++)add(S,n*2+i,1);
    for(int i=1;i<=D;i++)add(n*2+F+i,T,1);
    for(int i=1;i<=n;i++){
        add(i,n+i,1);
        int a,b,x;
        cin>>a>>b;
        while(a--){
            cin>>x;
            add(n*2+x,i,1);
        }
        while(b--){
            cin>>x;
            add(n+i,n*2+F+x,1);
        }
    }
    cout<<dinic()<<"\n";
}

POJ3498/UVA12125 企鹅游行 ​

题意：
一张二维图，给定n个点和企鹅的跳跃能力D，每个点上有ai只企鹅，bi次能用的起跳次数(超过就碎掉),问能否有一个点聚集所有的企鹅 思路：

  • 初始有多少企鹅就从S连多少的边
  • 枚举每个点能跳跃到的点，连正无穷边
  • 枚举一个点当汇点跑dinic
    • 还原流量fi+=fi1fi1=0f_i+=f_{i^1} f_{i^1}=0
cpp
const int N=210,M=21000;
int h[N],e[M],ne[M],f[M],idx;
int d[N],cur[N];
int n,S,T;
double D;
PII p[N];
void add(int a,int b,int c){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    q.push(S);
    d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                d[v]=d[u]+1;
                cur[v]=h[v];
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int v=e[i];
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())while(flow=find(S,INF))r+=flow;
    return r;
}
bool check(PII a,PII b){
    double x=a.x-b.x;
    double y=a.y-b.y;
    return x*x+y*y<D+1e-8;
}
void solve(){
    memset(h,-1,sizeof h);
    idx=0;
    cin>>n>>D;
    D*=D;
    S=0;
    int tot=0;
    for(int i=1;i<=n;i++){
        cin>>p[i].x>>p[i].y;
        int a,b;
        cin>>a>>b;
        add(S,i,a),tot+=a;
        add(i,n+i,b);
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(check(p[i],p[j])){
                add(n+i,j,INF);
                add(n+j,i,INF);
            }
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        T=i;
        for(int j=0;j<idx;j+=2){
            f[j]+=f[j^1];
            f[j^1]=0;
        }
        if(dinic()==tot){
            cout<<i-1<<" ";
            cnt++;
        }
    }
    if(!cnt)cout<<"-1";
    cout<<"\n";
}

SP4063/POJ1149 PIGS ​

题意：
有m个猪圈，n个顾客，每个顾客需要b只猪，顾客有猪圈的钥匙，每一个顾客来(按顺序)打开一些猪圈，拿走一些猪，然后可以重新分配开了的猪圈的猪，下一个顾客来之前把猪圈关上，问最多能卖多少只猪
思路：

  • 如果没有重新分配的条件，则题目转化为两组点求最大流
  • 如果没有顺序，那么从顾客反向连一条容量(为他能拿到所有的猪的数量)的边，求最大流
  • 有顺序做法：
    • 对于一个猪圈，如果它之前没有被开过，那么直接从源点连向顾客
    • 否则从上一个顾客连流量为无穷的边到现在的顾客

最小割 ​

Networks Wars(01分数规划+最小割) ​

题意： 给定带权无向图G=(V,E)，每条边有容量We，将点s和t分开的一个边割集C，使割集的平均边权最小，即最小化∑e∈cwe∣C∣给定带权无向图G=(V,E)，每条边有容量W_e，将点s和t分开的一个边割集C，使割集的平均边权最小，即最小化 \frac{\sum _{e∈c}w_e }{|C|}这里边割集指删去这些边，s与t不再联通这里边割集指删去这些边，s与t不再联通 思路：

  • 假设∑e∈cwe∣C∣>λ假设\frac{\sum _{e∈c}w_e }{|C|}>\lambda
  • ∑e∈cwe>∣C∣⋅λ即∑e∈cwe−∣C∣⋅λ>0即∑e∈c(we−λ)>0\sum _{e∈c}w_e>|C| \cdot \lambda 即\sum _{e∈c}w_e-|C| \cdot \lambda>0即\sum _{e∈c}(w_e- \lambda)>0
  • <亦是如此,因此可以二分
  • 这里的边割集可以是所有令s,t断开的边加上若干条无关边(集合就与流网络的边割集不一样了，即可以选集合S,T的内部边)
    • 对于w'[i]=w[i]-lambda,如果<=0则不管有没有关都选上，一定会让答案更小
    • 对于所有>0肯定是越少选越好，即不要选集合内部边，这就和流网络的集合对应上了，就可以用网络流来解
cpp
const int N=105,M=805;
const double eps=1e-8,inf=1e8;
int n,m,S,T;
int h[N],e[M],ne[M],w[M],idx;
double f[M];
int d[N],hh,tt,q[N],cur[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    d[S]=hh=tt=0;
    q[0]=S;
    cur[S]=h[S];
    while(hh<=tt)
    {
        int x=q[hh++];
        for(int i=h[x];~i;i=ne[i])
        {
            int y=e[i];
            if(d[y]==-1&&f[i])
            {
                d[y]=d[x]+1;
                cur[y]=h[y];
                if(y==T)return true;
                q[++tt]=y;
            }
        }
    }
    return false;
}
double dfs(int x,double limit)
{
    if(x==T)return limit;
    double flow=0;
    for(int i=cur[x];~i&&flow<limit;i=ne[i])
    {
        cur[x]=i;
        int y=e[i];
        if(d[y]==d[x]+1&&f[i])
        {
            double t=dfs(y,min(f[i],limit-flow));
            if(!t)d[y]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
bool dinic(double x)
{
    double res=0;
    for(int i=0;i<idx;i+=2)
        if(w[i]<=x)res+=w[i]-x,f[i]=f[i^1]=0;
        else
            f[i]=f[i^1]=w[i]-x;
    double flow=0;
    while(bfs())while((flow=dfs(S,inf))>0)res+=flow;
    return res<=0;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d%d%d",&n,&m,&S,&T);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z),add(y,x,z);
    }
    double l=1,r=1e7;
    while(fabs(r-l)>eps)
    {
        double mid=(l+r)/2;
        if(dinic(mid))r=mid;
        else
            l=mid;
    }
    printf("%.2lf",l);
    return 0;
}

SP839 OPTM - Optimal Marks ​

给你一个无向图G（V，E）。 每个顶点都有一个int范围内的整数的标记。 不同的顶点可能有相同的标记。

对于边（u，v），我们定义Cost（u，v）= mark [u] xor mark [v]。

现在我们知道某些节点的标记了。你需要确定其他节点的标记，以使边的总成本尽可能小。

如果有多解，请输出∑marki\sum mark_i最小的方案。如果仍有多解，输出任意一个。

思路：

  • 每一位互不影响，最终求和即可
  • mark为0/1,则可以划分0和1两个集合，转换为在该图求最小割容量(边权对应容量)
    • 对于初始为0的点，与源点连无穷边，则它一定不会形成割边(无法满流)，1的点向汇点连无穷边
  • 然后如果问题求的最大值，应该是每一位dinic(i)<<i,但是这题题意求所有点的对应数
    • 那么如果当前点存在增广路到达T即d[i]!=-1，则加上当前数位值
cpp
const int N=510,M=(3000+N*2)*2;
int h[N],e[M],ne[M],f[M],idx;
int d[N],cur[N],p[N],ans[N];
int n,m,S,T;
PII edges[3010];
void add(int a,int b,int c,int d){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=d,ne[idx]=h[b],h[b]=idx++;
}
bool bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    q.push(S);
    d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                d[v]=d[u]+1;
                cur[v]=h[v];
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int v=e[i];
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())while(flow=find(S,INF))r+=flow;
    return r;
}
void build(int k){
    memset(h,-1,sizeof h);
    S=0,T=n+1;
    idx=0;
    for(int i=1;i<=n;i++){
        if(p[i]>=0){
            if(p[i]>>k&1)add(S,i,INF,0);
            else add(i,T,INF,0);
        }
    }
    for(int i=1;i<=m;i++)add(edges[i].x,edges[i].y,1,1);
    dinic();
    for(int i=1;i<=n;i++){
        if(d[i]!=-1)ans[i]|=(1ll<<k);
    }
}
void solve(){
    memset(p,-1,sizeof p);
    memset(ans,0,sizeof ans);
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>edges[i].x>>edges[i].y;
    int k;
    cin>>k;
    while(k--){
        int x,y;
        cin>>x>>y;
        p[x]=y;
    }
    for(int i=0;i<31;i++)build(i);
    for(int i=1;i<=n;i++)cout<<ans[i]<<"\n";
}

最小割之最大权闭合图 ​

闭合子图：一个点集，点的所有边都指向点的内部，然后包含这些点的所有边 最大权闭合图：集合内的点权总和最大

  • 建图，对于原图的边全用无穷边代替
    • 对于点权大于等于0的点，与S相连
    • 对于点权小于0的点，与T相连
    • 边权均为绝对值
  • 定义简单割：流网络中，割集中的边只会在与S,T相连的边上
    • 证明：闭合子图<=>简单割
    • 对于一个闭合子图的点集v1来讲，对应于流网络的点集v1+S,那么点集的点不会走到另外一个集合，因此割边不会出现在原图的边中，即一个简单割
    • 反之亦然
  • 计算简单割的流量C(S,T),这里源点和汇点为s,t
    • S=v1+s,T=v2+t则有四种边
      • v1->v2因为简单割割边不会出现在原图的边上，所以这种边不存在
      • s->v2，存在
      • v1->t，存在
      • s->t，显然不存在
    • 因此C(S,T)=C(s,v2)+C(v1,t)=∑v∈v2+wv+∑v∈v1−(−wv)因此C(S,T)=C(s,v2)+C(v1,t)= \sum _{v∈v_2^+}w_v + \sum _{v∈v_1^-}(-w_v)
    • wv1=∑v∈v1+wv−∑v∈v1−(−wv)w_{v_1}= \sum _{v∈v_1^+} w_v - \sum _{v∈v_1^-} (-w_v)
    • 上诉两式相加得C(S,T)+wv1=∑v∈v2+wv+∑v∈v1+wv=∑为正数的点集wv上诉两式相加得 C(S,T)+w_{v_1}=\sum _{v∈v_2^+}w_v+\sum _{v∈v_1^+} w_v= \sum _{为正数的点集}w_v
    • 那么右边为定值，要让W_v最大即简单割最小
    • 而简单割的割边一定不可能在原图边上(因为容量无穷),因此最小割也为简单割
    • 因此求最小割，利用最终式子就能得到最大权子图了

P4174 [NOI2006] 最大获利 ​

题意：
有n个通信站，m个公司，每个公司有三个参数a b c，如果建立了a,b两个通信站，则获利c元，建立通信站花费pi 思路：
等价于向a,b连边,通信站设为负值，则转化为求最大权闭合子图

cpp
#include<bits/stdc++.h>
#define ll long long
#define x first
#define y second
const int mod=19930726;
const int INF=0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
const int N=55010,M=(N+5e4*2)*2;
int h[N],e[M],ne[M],f[M],idx;
int d[N],cur[N];
int n,m,S,T;
void add(int a,int b,int c){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    q.push(S);
    d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                d[v]=d[u]+1;
                cur[v]=h[v];
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int v=e[i];
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())while(flow=find(S,INF))r+=flow;
    return r;
}
void solve(){
    cin>>n>>m;
    S=0,T=n+m+1;
    int tot=0;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++){
        int p;
        cin>>p;
        add(m+i,T,p);
    }
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(S,i,c);
        tot+=c;
        add(i,m+a,INF);
        add(i,m+b,INF);
    }
    cout<<tot-dinic()<<"\n";
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}

最小割之最大密度子图 ​

在G(V,E)中选择一个V'和E'，使得对于任意一条边(E'内)的u,v,都有u∈V' and v∈V'最大化∣E′∣∣V′∣最大化\frac{|E'|}{|V'|}

  • 令∣E′∣∣V′∣=g,则按照01分数规划的思想，可以看出最大化∣E′∣−g∣V′∣令\frac{|E'|}{|V'|}=g,则按照01分数规划的思想，可以看出最大化|E'|-g|V'|
    img

UVA1389Hard Life(黑题) ​

过于抽象，待补。。。

最小割之最小权点覆盖 ​

最小权点覆盖，在图中选最小的点，能覆盖所有边 二分图中，最大匹配数=最小点覆盖数=n(若有权值则表示总权值)-最大独立集数(权值大于1仍成立)

  • 建图，左边点向S连容量为点权的边，右边向T连容量为点权的边，左右两边建无穷边
  • 可证：点覆盖集<=>简单割
  • 因此求流网络最小割就好

POJ2125 Destroying The Graph ​

题意：
IMG
思路：
拆点，一个点拆成出去-和进来+的
左边为+，右边为-就是一张二分图，求最小权点覆盖

  • 找割边
    • 从源点出发能到达的为S,其余为T
    • 枚举所有正向边，若两点为S->T即为割边

最小割之最大权独立集 ​

独立集：选出的点集中不存在边

  • 任意的点覆盖集的补集都是独立集
    • 证明：假设点覆盖集为v1,v2=v−v1假设点覆盖集为v_1,v_2=v-v_1
    • 假设v2存在两个点之间存在边，则v1不存在这两个点，则v1不是点覆盖集，与假设矛盾假设v_2存在两个点之间存在边，则v_1不存在这两个点，则v_1不是点覆盖集，与假设矛盾
    • 所以v2不存在两个点有边，v2为独立集所以v_2不存在两个点有边，v_2为独立集

P4474王者之剑 ​

题意： n*m的网格，每个网格有 vi,jv_{i,j} 个宝石，可以决定从哪里开始走

  • 第i秒开始时，如果有宝石，捡起第i秒开始时，如果有宝石，捡起
  • 偶数秒周围四格宝石消失
  • 下一秒可以在上下左右或者原点位置
    求最多拿宝石的数量 思路：
  • 分析可得只有偶数秒能取宝石
  • 不可能同时拿走相邻宝石(可以发现为一个独立集)(合法方案=>独立集)
  • 证明：独立集=>合法方案
    • 可以通过停顿一次来重置奇偶性，来拿到所有独立集的点
cpp
const int N=10010,M=60010;
int h[N],e[M],ne[M],f[M],idx;
int d[N],cur[N];
int n,m,S,T;
void add(int a,int b,int c){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    q.push(S);
    d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                d[v]=d[u]+1;
                cur[v]=h[v];
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int v=e[i];
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())while(flow=find(S,INF))r+=flow;
    return r;
}
int get(int x,int y){
    return (x-1)*m+y;
}
void solve(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    S=0,T=n*m+1;
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    int tot=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int w;
            cin>>w;
            if(i+j&1){
                add(S,get(i,j),w);
                for(int k=0;k<4;k++){
                    int x=i+dx[k],y=j+dy[k];
                    if(x>=1&&x<=n&&y>=1&&y<=m){
                        add(get(i,j),get(x,y),INF);
                    }
                }
            }
            else add(get(i,j),T,w);
            tot+=w;
        }
    }
    cout<<tot-dinic()<<"\n";
}

SP300 CABLETV - Cable TV Network ​

题意：
给定一个n(n <= 50)个点的无向图，求它的点联通度。即最少删除多少个点，使得图不连通。 思路：

  • 图不连通最开始的情况肯定是分成两个集合，因此想到最小割
  • 题目是删点而不是删边，因此可以考虑拆点，一个点拆成入点和出点，容量为1;原图边容量为无穷(这样就不会是割边，就不会拆边)
  • 定义简单割为割边只在点内部，易证：简单割<=>极小点集
  • 枚举两个点当源点和汇点，跑最小割，所有最小割取min
cpp
const int N=110,M=52000;
int h[N],e[M],ne[M],f[M],idx;
int d[N],cur[N];
int n,m,S,T;
void add(int a,int b,int c){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    q.push(S);
    d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                d[v]=d[u]+1;
                cur[v]=h[v];
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int v=e[i];
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())while(flow=find(S,INF))r+=flow;
    return r;
}
int get(int x,int y){
    return (x-1)*m+y;
}
void solve(){
    while(cin>>n>>m){
        memset(h,-1,sizeof h);
        idx=0;
        for(int i=0;i<n;i++)add(i,n+i,1);
        for(int i=1;i<=m;i++){
            int u,v;
            scanf(" (%d,%d)",&u,&v);
            add(u+n,v,INF);
            add(v+n,u,INF);
        }
        int res=n;
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                S=n+i,T=j;
                for(int k=0;k<idx;k+=2){
                    f[k]+=f[k^1];
                    f[k^1]=0;
                }
                res=min(res,dinic());
            }
        }
        cout<<res<<"\n";
    }
}

P2762 太空飞行计划问题(最大权闭合子图) ​

题意：
有E={E1,E2,..}的实验,I={I1,I2,..}的仪器,实验可以获利，购买仪器需要钱，求最大净利润
思路：
裸的跑最大权闭合子图

  • 找方案：
    • S集合中所有的实验和仪器
cpp
const int N=110,M=5200;
int h[N],e[M],ne[M],f[M],idx;
int d[N],cur[N];
int n,m,S,T;
void add(int a,int b,int c){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    q.push(S);
    d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(d[v]==-1&&f[i]){
                d[v]=d[u]+1;
                cur[v]=h[v];
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int v=e[i];
        if(d[v]==d[u]+1&&f[i]){
            int t=find(v,min(f[i],limit-flow));
            if(!t)d[v]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())while(flow=find(S,INF))r+=flow;
    return r;
}
bool st[N];
void dfs(int u){
    st[u]=true;
    for(int i=h[u];~i;i=ne[i]){
        if(!st[e[i]]&&f[i])dfs(e[i]);
    }
}
void solve(){
    cin>>m>>n;
    S=0,T=n+m+1;
    memset(h,-1,sizeof h);
    getchar();
    int tot=0;
    for(int i=1;i<=m;i++){
        int w,id;
        string line;
        getline(cin,line);
        stringstream ssin(line);
        ssin>>w;
        add(S,i,w);
        while(ssin>>id)add(i,m+id,INF);
        tot+=w;
    }
    for(int i=1;i<=n;i++){
        int p;
        cin>>p;
        add(m+i,T,p);
    }
    int res=dinic();
    dfs(S);
    for(int i=1;i<=m;i++){
        if(st[i])cout<<i<<" ";
    }
    cout<<"\n";
    for(int i=m+1;i<=m+n;i++){
        if(st[i])cout<<i-m<<" ";
    }
    cout<<"\n";
    cout<<tot-res<<"\n";
}

P3355 骑士共存问题(最大权独立集) ​

题意： 马(象棋走法)可以攻击八个方向的点，问在n*n中能放多少个马
思路：
i+j分奇偶，就是一个最大权独立集
最小割求即可

费用流(所有最大流中的费用最大值/最小值) ​

总费用等于流量*当前的边的费用

最小费用最大流 ​

顾名思义，最大流中费用最小的

  • 将EK算法的bfs换成spfa，沿着最短路增广的费用一定更小
  • 局限：无负权环
  • 费用：w(u,v)=-w(v,u)

模板 ​

cpp
const int N=5010,M=100010;
int h[N],e[M],f[M],w[M],ne[M],idx;
int d[N],mxf[N],pre[N];//d表示最短距离，mxf表示最大流,pre表示到i的边的编号
int n,m,S,T;
bool vis[N];
void add(int a,int b,int c,int d){
    e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool spfa(){
    queue<int> q;
    memset(d,0x3f,sizeof d);
    memset(mxf,0,sizeof mxf);
    q.push(S);
    d[S]=0,mxf[S]=INF;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(f[i]&&d[v]>d[u]+w[i]){
                d[v]=d[u]+w[i];
                pre[v]=i;
                mxf[v]=min(f[i],mxf[u]);
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return mxf[T]>0;
}   
void EK(int &flow,int &cost){
    flow=cost=0;
    while(spfa()){
        int t=mxf[T];
        flow+=t,cost+=t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1]){
            f[pre[i]]-=t;
            f[pre[i]^1]+=t;
        }
    }
}
void solve(){
    cin>>n>>m>>S>>T;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        add(a,b,c,d);
    }
    int flow,cost;
    EK(flow,cost);
    cout<<flow<<" "<<cost<<"\n";
}

模板2 ​

cpp
int h[N],e[M],f[M],w[M],ne[M],idx;
int dis[N],cur[N];//d表示最短距离,cur为当前弧
int n,m,S,T;
bool vis[N];
int height[N];// 势能函数
vector<int> dot;// 点数
void add(int a,int b,int c,int d){
    e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool dijk(){
    for(auto &i:dot)dis[i]=INF,cur[i]=h[i];
	priority_queue<PII,vector<PII>,greater<>> pq;
	dis[S]=0;
    pq.emplace(0,S);
    while(!pq.empty()){
		auto [d,u]=pq.top();
		pq.pop();
		if(dis[u]!=d)continue;
		for(int i=h[u];~i;i=ne[i]){
			int v=e[i];
			if(f[i]&&dis[v]>d+height[u]-height[v]+w[i]){
				dis[v]=d+height[u]-height[v]+w[i];
				pq.emplace(dis[v],v);
			}
		}
    }
    return dis[T]!=INF;
}   
int find(int u,int limit){
	if(!limit||u==T)return limit;
	int flow=0;
	vis[u]=1;
    for(int &i=cur[u];~i&&flow<limit;i=ne[i]){
        int v=e[i];
        if(dis[v]==dis[u]+height[u]-height[v]+w[i]&&f[i]&&!vis[v]){
            int t=find(v,min(f[i],limit-flow));
            f[i]-=t,f[i^1]+=t,flow+=t;
			if(flow==limit)break;
        }
    }
	vis[u]=0;
    return flow;
}
void mcmf(int &flow,int &cost){
	flow=cost=0;
	int r;
	while(dijk()){
		int r=find(S,INF);
		flow+=r;
		for(auto &i:dot)height[i]+=dis[i];
		cost+=height[T]*r;
	}
}

费用流封装版 ​

cpp
struct Flow{
    int n,S,T,idx;
    vector<int> h,e,f,w,ne;
    vector<int> dis,cur,height;// d表示最短距离,cur为当前弧,height为势能函数
    vector<bool> vis;
    Flow(){}
    Flow(int n){
        init(n);
    }
    void init(int n,int S=0,int T=0){
        h.assign(n+1,-1);
        dis.assign(n+1,0);
        cur.assign(n+1,0);
        height.assign(n+1,0);
        vis.assign(n+1,0);
        e.clear();
        ne.clear();
        f.clear();
        w.clear();
        idx=0;
        this->n=n;
        this->S=S;
        this->T=T==0?n:T;
    }
    void newEdge(int x=2){
        for(int i=0;i<x;i++){
            e.emplace_back();
            ne.emplace_back();
            f.emplace_back();
            w.emplace_back();
        }
    }
    void addEdge(int a,int b,int c,int d){
        newEdge();
        e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
        e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
    }
    bool dijk(){
        for(int i=0;i<=n;i++)dis[i]=INF,cur[i]=h[i];
        priority_queue<PII,vector<PII>,greater<>> pq;
        dis[S]=0;
        pq.emplace(0,S);
        while(!pq.empty()){
            auto [d,u]=pq.top();
            pq.pop();
            if(dis[u]!=d)continue;
            for(int i=h[u];~i;i=ne[i]){
                int v=e[i];
                if(f[i]&&dis[v]>d+height[u]-height[v]+w[i]){
                    dis[v]=d+height[u]-height[v]+w[i];
                    pq.emplace(dis[v],v);
                }
            }
        }
        return dis[T]!=INF;
    }  
    int find(int u,int limit){
        if(!limit||u==T)return limit;
        int flow=0;
        vis[u]=1;
        for(int &i=cur[u];~i&&flow<limit;i=ne[i]){
            int v=e[i];
            if(dis[v]==dis[u]+height[u]-height[v]+w[i]&&f[i]&&!vis[v]){
                int t=find(v,min(f[i],limit-flow));
                f[i]-=t,f[i^1]+=t,flow+=t;
                if(flow==limit)break;
            }
        }
        vis[u]=0;
        return flow;
    }
    void mcmf(int &flow,int &cost){
        flow=cost=0;
        int r;
        while(dijk()){
            int r=find(S,INF);
            flow+=r;
            for(int i=0;i<=n;i++)height[i]+=dis[i];
            cost+=height[T]*r;
        }
    }
};

有源汇上下界费用流 ​

  • 这里的费用流不需要满流，只需要符合条件就行

步骤：

  • 先把原图的边连了
  • 然后汇点tt向ss连(0,∞,0)(0,\infty ,0)
  • 计算每个点的流入流出FiF_i
  • Fi>0F_i \gt 0,附加源点SS向ii连(0,Fi,0)(0,F_i,0)
  • 否则，ii向附加汇点TT连(0,−Fi,0)(0,-F_i,0)
  • 原图可行费用流=新图最大流费用流+∑Lowi⋅wi\sum Low_i \cdot w_i（即该条边的下界*该条边的费用）
cpp
int h[N],e[M],f[M],w[M],ne[M],Low[M],idx;
int dis[N],cur[N];//d表示最短距离,cur为当前弧
int n,m,S,T;
bool vis[N];
int height[N];// 势能函数
vector<int> dot;// 点数
void add(int a,int b,int c,int d,int val){
    e[idx]=b,f[idx]=d-c,w[idx]=val,Low[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-val,ne[idx]=h[b],h[b]=idx++;
}
bool dijk(){
    for(auto &i:dot)dis[i]=INF,cur[i]=h[i];
	priority_queue<PII,vector<PII>,greater<>> pq;
	dis[S]=0;
    pq.emplace(0,S);
    while(!pq.empty()){
		auto [d,u]=pq.top();
		pq.pop();
		if(dis[u]!=d)continue;
		for(int i=h[u];~i;i=ne[i]){
			int v=e[i];
			if(f[i]&&dis[v]>d+height[u]-height[v]+w[i]){
				dis[v]=d+height[u]-height[v]+w[i];
				pq.emplace(dis[v],v);
			}
		}
    }
    return dis[T]!=INF;
}   
int find(int u,int limit){
	if(!limit||u==T)return limit;
	int flow=0;
	vis[u]=1;
    for(int &i=cur[u];~i&&flow<limit;i=ne[i]){
        int v=e[i];
        if(dis[v]==dis[u]+height[u]-height[v]+w[i]&&f[i]&&!vis[v]){
            int t=find(v,min(f[i],limit-flow));
            f[i]-=t,f[i^1]+=t,flow+=t;
			if(flow==limit)break;
        }
    }
	vis[u]=0;
    return flow;
}
void mcmf(int &flow,int &cost){
	flow=cost=0;
	int r;
    for(auto &i:dot)height[i]=0;
	while(dijk()){
		int r=find(S,INF);
		flow+=r;
		for(auto &i:dot)height[i]+=dis[i];
		cost+=height[T]*r;
	}
}
void clear(){
    for(auto &i:dot)h[i]=-1;
    dot.clear();
    for(int i=0;i<idx;i++)e[i]=f[i]=w[i]=ne[i]=Low[i]=0;
    idx=0;
}
void solve() {
    clear();
    cin>>n>>m;
    int s=0,t=m+2*n+2;
    S=m+2*n+3,T=m+2*n+4;
    vector<int> F(m+2*n+3);// 出入
    for(int i=0;i<=m+2*n+4;i++)dot.push_back(i);
    for(int i=1;i<=m;i++){
        int l;
        cin>>l;
        add(s,i,l,INF,0);
        F[s]-=l,F[i]+=l;
    }
    vector<int> c(2*n+1),v(2*n+1);
    for(int i=1;i<=2*n;i++)cin>>c[i];
    for(int i=1;i<=2*n;i++)cin>>v[i];
    for(int i=1;i<=2*n;i++){
        add(c[i],i+m,0,1,-v[i]);
        add(i+m,i+m+1,(i+1)/2,INF,0);
        F[i+m]-=(i+1)/2,F[i+m+1]+=(i+1)/2;
    }
    add(m+2*n+1,t,n,n,0);
    F[m+2*n+1]-=n,F[t]+=n;
    int tot=0;
    for(int i=0;i<=m+2*n+2;i++){
        if(F[i]>0)add(S,i,0,F[i],0),tot+=F[i];
        else add(i,T,0,-F[i],0);
    }
    add(t,s,0,INF,0);
    int flow,cost;
    mcmf(flow,cost);
    // cout<<flow<<" "<<cost<<"\n";
    if(flow!=tot){
        cout<<"-1\n";
        return;
    }
    int res=-cost;
    for(int i=0;i<idx;i+=2){
        res+=Low[i]*w[i];
    }
    cout<<res<<"\n";
}

P4015 运输问题(最小+最大) ​

思路：

  • 运输方案<=>最大流
  • 最小花费最大流
  • 最大求法：
    • 将所有费用取反
    • 求最小费用，再取反
cpp
int h[N],e[M],f[M],w[M],ne[M],idx;
int d[N],mxf[N],pre[N];//d表示最短距离，mxf表示最大流,pre表示到i的边的编号
int n,m,S,T;
bool vis[N];
void add(int a,int b,int c,int d){
    e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool spfa(){
    queue<int> q;
    memset(d,0x3f,sizeof d);
    memset(mxf,0,sizeof mxf);
    q.push(S);
    d[S]=0,mxf[S]=INF;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(f[i]&&d[v]>d[u]+w[i]){
                d[v]=d[u]+w[i];
                pre[v]=i;
                mxf[v]=min(f[i],mxf[u]);
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return mxf[T]>0;
}   
void EK(int &flow,int &cost){
    flow=cost=0;
    while(spfa()){
        int t=mxf[T];
        flow+=t,cost+=t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1]){
            f[pre[i]]-=t;
            f[pre[i]^1]+=t;
        }
    }
}
void solve(){
    cin>>m>>n;
    S=0,T=n+m+1;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        add(S,i,x,0);
    }
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        add(m+i,T,x,0);
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            int c;
            cin>>c;
            add(i,m+j,INF,c);
        }
    }
    int flow,cost;
    EK(flow,cost);
    cout<<cost<<"\n";
    for(int i=0;i<idx;i+=2){
        f[i]+=f[i^1],f[i^1]=0;
        w[i]=-w[i],w[i^1]=-w[i^1];
    }
    EK(flow,cost);
    cout<<-cost;
}

负载平衡问题 ​

题意：
n个仓库组成一个环形，每个仓库可以向相邻点搬运货物，问所有仓库货物相等时，最少搬运量 思路：

  • 求出平均值x
  • 对于大于x的仓库，说明货需要出去，连到源点
  • 对于小于x的仓库，说明货要进来，连到汇点
  • 这样对于每个可行方案都会对应一个最大流
  • 则求最小费用，一条边的费用为1
cpp
const int N=110,M=1010;
int h[N],e[M],f[M],w[M],ne[M],idx;
int d[N],mxf[N],pre[N],s[N];//d表示最短距离，mxf表示最大流,pre表示到i的边的编号
int n,m,S,T;
bool vis[N];
void add(int a,int b,int c,int d){
    e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool spfa(){
    queue<int> q;
    memset(d,0x3f,sizeof d);
    memset(mxf,0,sizeof mxf);
    q.push(S);
    d[S]=0,mxf[S]=INF;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(f[i]&&d[v]>d[u]+w[i]){
                d[v]=d[u]+w[i];
                pre[v]=i;
                mxf[v]=min(f[i],mxf[u]);
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return mxf[T]>0;
}   
void EK(int &flow,int &cost){
    flow=cost=0;
    while(spfa()){
        int t=mxf[T];
        flow+=t,cost+=t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1]){
            f[pre[i]]-=t;
            f[pre[i]^1]+=t;
        }
    }
}
void solve(){
    cin>>n;
    S=0,T=n+1;
    int tot=0;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++){
        cin>>s[i],tot+=s[i];
        add(i,i>1?i-1:n,INF,1);
        add(i,i<n?i+1:1,INF,1);
    }
    tot/=n;
    for(int i=1;i<=n;i++){
        if(s[i]>tot)add(S,i,s[i]-tot,0);
        else add(i,T,tot-s[i],0);
    }
    int flow,cost;
    EK(flow,cost);
    cout<<cost<<"\n";
}

分配问题(二分图最优匹配) ​

题意：
n个工作分配给n个人，第i个人做第j个工作的费用为C_{i,j}求最大和最小花费
思路： 二分图，跑模板

数字梯形问题(拆点+费用流) ​

给定一个第一行为m个点，有n行的类似杨辉三角的梯形，从第一行每个点往下走m条路经，求最大总和 分别求满足以下三个规则的最大值：

  1. 从梯形的顶至底的 m 条路径互不相交；
  2. 从梯形的顶至底的 m 条路径仅在数字结点处相交；
  3. 从梯形的顶至底的 m 条路径允许在数字结点相交或边相交。 思路：
  • 考虑规则1
    • 对于每个点只能走一次，可以考虑拆点，入点和出点连容量为1，费用为点数的边
    • 最上面点连源点，容量为1,费用为0
    • 最下面连汇点，容量1费用0
    • 按题意每个点连容量1费用0
  • 对于规则2，两条路径可以交叉在一个点
    • 即放开点内部的容量，连向其他的点容量仍为1，因此保证从当前点到下一个点不会被走两次
    • 往汇点的容量也放开，因为，多路径在最后一行汇集是合法的
  • 对于规则3，在2的基础上
    • 放开边的限制
cpp
const int N=1100,M=4000;
int h[N],e[M],f[M],w[M],ne[M],idx;
int d[N],mxf[N],pre[N];//d表示最短距离，mxf表示最大流,pre表示到i的边的编号
int n,m,S,T;
bool vis[N];
int id[40][40],C[40][40];
void add(int a,int b,int c,int d){
    e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool spfa(){
    queue<int> q;
    memset(d,0x3f,sizeof d);
    memset(mxf,0,sizeof mxf);
    q.push(S);
    d[S]=0,mxf[S]=INF;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(f[i]&&d[v]>d[u]+w[i]){
                d[v]=d[u]+w[i];
                pre[v]=i;
                mxf[v]=min(f[i],mxf[u]);
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return mxf[T]>0;
}   
void EK(int &flow,int &cost){
    flow=cost=0;
    while(spfa()){
        int t=mxf[T];
        flow+=t,cost+=t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1]){
            f[pre[i]]-=t;
            f[pre[i]^1]+=t;
        }
    }
}
void solve(){
    cin>>m>>n;
    int cnt=0;
    S=++cnt;
    T=++cnt;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m+i-1;j++){
            id[i][j]=++cnt;
            cin>>C[i][j];
        }
    }
    int flow,cost;
    //规则1
    memset(h,-1,sizeof h);
    idx=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m+i-1;j++){
            add(id[i][j]*2,id[i][j]*2+1,1,-C[i][j]);
            if(i==1)add(S,id[i][j]*2,1,0);
            if(i==n)add(id[i][j]*2+1,T,1,0);
            if(i<n){
                add(id[i][j]*2+1,id[i+1][j]*2,1,0);
                add(id[i][j]*2+1,id[i+1][j+1]*2,1,0);
            }
        }
    }
    EK(flow,cost);
    cout<<-cost<<"\n";
    //规则2
    memset(h,-1,sizeof h);
    idx=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m+i-1;j++){
            add(id[i][j]*2,id[i][j]*2+1,INF,-C[i][j]);
            if(i==1)add(S,id[i][j]*2,1,0);
            if(i==n)add(id[i][j]*2+1,T,1,0);
            if(i<n){
                add(id[i][j]*2+1,id[i+1][j]*2,1,0);
                add(id[i][j]*2+1,id[i+1][j+1]*2,1,0);
            }
        }
    }
    EK(flow,cost);
    cout<<-cost<<"\n"; 
    //规则3
    memset(h,-1,sizeof h);
    idx=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m+i-1;j++){
            add(id[i][j]*2,id[i][j]*2+1,INF,-C[i][j]);
            if(i==1)add(S,id[i][j]*2,1,0);
            if(i==n)add(id[i][j]*2+1,T,INF,0);
            if(i<n){
                add(id[i][j]*2+1,id[i+1][j]*2,INF,0);
                add(id[i][j]*2+1,id[i+1][j+1]*2,INF,0);
            }
        }
    }
    EK(flow,cost);
    cout<<-cost<<"\n";
}

费用流之网格数问题 ​

P2045 方格取数加强版(K取方格数) ​

题意：
从(1,1)开始走，每次只能向右或向下走，走到(n,n)，走k次，每个数只能取一次，求最大能取的值 思路：

  • 拆点，点权转边权，建容量为1的费用为点权的边
    • 因为下一次仍能走这个点，所以还要建容量为无穷费用为0的边
  • 然后源点与(1,1),(n,n)与汇点,每个能走到的点连边，容量无穷费用0
cpp
const int N=5010,M=20010;
int h[N],e[M],f[M],w[M],ne[M],idx;
int d[N],mxf[N],pre[N];//d表示最短距离，mxf表示最大流,pre表示到i的边的编号
int n,k,S,T;
bool vis[N];
void add(int a,int b,int c,int d){
    e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool spfa(){
    queue<int> q;
    memset(d,0x3f,sizeof d);
    memset(mxf,0,sizeof mxf);
    q.push(S);
    d[S]=0,mxf[S]=INF;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(f[i]&&d[v]>d[u]+w[i]){
                d[v]=d[u]+w[i];
                pre[v]=i;
                mxf[v]=min(f[i],mxf[u]);
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return mxf[T]>0;
}   
void EK(int &flow,int &cost){
    flow=cost=0;
    while(spfa()){
        int t=mxf[T];
        flow+=t,cost+=t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1]){
            f[pre[i]]-=t;
            f[pre[i]^1]+=t;
        }
    }
}
int get(int x,int y,int t){
    return (x-1)*n+y+t*n*n;
}
void solve(){
    cin>>n>>k;
    S=0,T=n*n*2+1;
    memset(h,-1,sizeof h);
    add(S,get(1,1,0),k,0);
    add(get(n,n,1),T,k,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int c;
            cin>>c;
            add(get(i,j,0),get(i,j,1),1,-c);
            add(get(i,j,0),get(i,j,1),INF,0);
            if(i+1<=n)add(get(i,j,1),get(i+1,j,0),INF,0);
            if(j+1<=n)add(get(i,j,1),get(i,j+1,0),INF,0);
        }
    }
    int flow,cost;
    EK(flow,cost);
    cout<<-cost<<"\n";
}

P4012 深海机器人问题 ​

与上题类似

P1251 餐巾计划问题 ​

题目描述 ​

一个餐厅在相继的 NN 天里，每天需用的餐巾数不尽相同。假设第 ii 天需要 rir_i 块餐巾（i=1,2,…,Ni = 1, 2, \dots, N）。餐厅可以购买新的餐巾，每块餐巾的费用为 pp 分；或者把旧餐巾送到快洗部，洗一块需 mm 天，其费用为 ff 分；或者送到慢洗部，洗一块需 nn 天（n>mn \gt m），其费用为 ss 分（s<fs \lt f）。

每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 NN 天中餐巾使用计划，使总的花费最小。编程找出一个最佳餐巾使用计划。

输入格式 ​

由标准输入提供输入数据。文件第 11 行有 11 个正整数 NN，代表要安排餐巾使用计划的天数。

接下来的一行是餐厅在相继的 NN 天里，每天需用的餐巾数。

最后一行包含 55 个正整数 p,m,f,n,sp, m, f, n, s。pp 是每块新餐巾的费用；mm 是快洗部洗一块餐巾需用天数；ff 是快洗部洗一块餐巾需要的费用；nn 是慢洗部洗一块餐巾需用天数；ss 是慢洗部洗一块餐巾需要的费用。

输出格式 ​

将餐厅在相继的 NN 天里使用餐巾的最小总花费输出。

样例 #1 ​

样例输入 #1 ​

3
1 7 5 
11 2 2 3 1

样例输出 #1 ​

134

提示 ​

对于 100%100 \% 的数据，1≤N≤2×1031 \le N \le 2 \times 10^3，1≤ri≤1071 \le r_i \le 10^7，1≤p,f,s≤1041 \le p, f, s \le 10^4。

思路 ​

  • 建图：
    • 左边为用过的毛巾(与源点连)，右边为需要的毛巾(与汇点连)
    • 那么对于左边的毛巾
      • 要么什么都不干，即流向下一天用过的毛巾
      • 要么通过快洗机，流向n天之后的需求毛巾
      • 要么通过慢洗机，流向m天之后的需求毛巾
    • 对于右边毛巾，除了来自快洗和慢洗，还要与源点连边，表示购买的毛巾
    • 那么流网络满流时，右边需求一定恰好满(因为源点流出去无穷量,但是源点流向用过的毛巾不一定满，它可以流向下一天用过最终被丢掉)
cpp
const int N=4010,M=(N+2000*4)*2;
int h[N],e[M],f[M],w[M],ne[M],idx;
int d[N],mxf[N],pre[N];//d表示最短距离，mxf表示最大流,pre表示到i的边的编号
int n,m,S,T;
int p,x,xp,y,yp,r[N];
bool vis[N];
void add(int a,int b,int c,int d){
    e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool spfa(){
    queue<int> q;
    memset(d,0x3f,sizeof d);
    memset(mxf,0,sizeof mxf);
    q.push(S);
    d[S]=0,mxf[S]=INF;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(f[i]&&d[v]>d[u]+w[i]){
                d[v]=d[u]+w[i];
                pre[v]=i;
                mxf[v]=min(f[i],mxf[u]);
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return mxf[T]>0;
}   
void EK(int &flow,int &cost){
    flow=cost=0;
    while(spfa()){
        int t=mxf[T];
        flow+=t,cost+=t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1]){
            f[pre[i]]-=t;
            f[pre[i]^1]+=t;
        }
    }
}
void solve(){
    cin>>n;
    S=0,T=2*n+1;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++){
        cin>>r[i];
    }
    cin>>p>>x>>xp>>y>>yp;
    for(int i=1;i<=n;i++){
        add(S,i,r[i],0);
        add(n+i,T,r[i],0);
        add(S,n+i,INF,p);
        if(i+1<=n)add(i,i+1,INF,0);
        if(i+x<=n)add(i,n+i+x,INF,xp);
        if(i+y<=n)add(i,n+i+y,INF,yp);
    }
    int flow,cost;
    EK(flow,cost);
    cout<<cost<<"\n";
}

P3980 [NOI2008] 志愿者招募 ​

  • nn天，第ii天需要aia_i人，有mm类人可以服务sis_i到tit_i天，费用为cc，问最小费用
  • 如果这个人第二天不干了，那么可以直接二分图
  • 但是这个人可能会干到下一天，因此需要重新建模
  • 每天看作一条边，ii向i+1i+1连边，源点向11连，n+1n+1向汇点连，流量为INF−aiINF-a_i，代表不工作的人最多的流量
  • 每类人sis_i向ti+1t_i+1连边，容量无穷，费用为cic_i，表示工作的人的通道
  • 最大流显然是INFINF
cpp
void solve(){
	memset(h,-1,sizeof h);
	int n,m;
	cin>>n>>m;
	S=0,T=n+2;
	for(int i=0;i<=n+2;i++)dot.push_back(i);
	add(S,1,INF,0);
	add(n+1,T,INF,0);
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		add(i,i+1,INF-x,0);
	}
	for(int i=1;i<=m;i++){
		int s,t,c;
		cin>>s>>t>>c;
		add(s,t+1,INF,c);
	}
	int flow,cost;
	mcmf(flow,cost);
	cout<<cost<<"\n";
}

费用流解法 ​

类似问题 ​

P2223 [HNOI2001] 软件开发 ​

​

模拟费用流 ​

模板：QOJ7185

题意：

一个二分图，左边n(≤50000)n(\leq 50000)个点，右边m(≤10)m(\leq 10)个点，左边ii匹配右边jj的花费为ci,jc_{i,j},右边每个点的容量为aia_i，求最小花费

  • 很明显可以用费用流直接解
  • 但是我们要学的是模拟费用流，这是一个经典模型

我们把一条增广路拆成三部分：

  1. 源点到第一个右部点(源点->第一个左部点->第一个右部点)
  2. 右部点->左部点->右部点->左部点->...
  3. 最后一个右部点到汇点

我们考虑这样一条路径：ii(右部点)到xx(左部点)到jj(右部点)

对应于网络流的定义即，原来的匹配(x,i)(x,i)取消，新的匹配(x,j)(x,j)生成

因此此时从ii到jj的最短路应该是cx,j−cx,ic_{x,j}-c_{x,i}，可以使用小根堆维护(i,j)(i,j)的最短路

因此我们对于右部点就建立出新的图，可以跑spfa，求出右部点点到汇点的最短路

然后贪心选取费用最小的点即可

一共增广nn次，spfa时间为m3m^3,更新小根堆复杂度为m2log⁡nm^2\log n

总时间复杂度O(n(m3+m2log⁡n))O(n(m^3+m^2\log n))

cpp
void solve() {
    int n,m;// n<=50000,m<=10
    cin>>n>>m;
    vector c(n+1,vector<int>(m+1));
    vector<int> lim(n+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cin>>c[i][j];// i->j的花费
    }
    for(int i=1;i<=m;i++)cin>>lim[i];// 容量
    vector s(m+1,vector<set<PII>>(m+1));// 路径i(右)->x(左)->j(右) ,维护a[x][j]-a[x][i]
    vector w(m+1,vector<int>(m+1));
    vector<int> be(n+1);// 左部点属于哪个右部点
    auto add=[&](int x,int id){
        be[x]=id;
        for(int i=1;i<=m;i++){
            if(i==id)continue;
            s[id][i].emplace(c[x][i]-c[x][id],x);
        }
    };
    auto del=[&](int x){
        int id=be[x];
        be[x]=-1;
        for(int i=1;i<=m;i++){
            if(i==id)continue;
            s[id][i].erase({c[x][i]-c[x][id],x});
        }
    };
    for(int i=1;i<=n;i++)add(i,0);
    queue<int> q;
    vector<int> dis(m+1),vis(m+1),pre(m+1);
    // dis为右部点到T的最小费用，vis为spfa辅助数组，pre记录前驱
    int ans=0;
    for(int t=1;t<=n;t++){// 枚举增广次数
        for(int i=0;i<=m;i++){
            pre[i]=-1;
            dis[i]=INF;
            for(int j=1;j<=m;j++){
                if(s[i][j].empty())w[i][j]=INF;
                else w[i][j]=s[i][j].begin()->first;
            }
        }
        q.push(0);
        dis[0]=0;
        vis[0]=1;
        pre[0]=0;
        while(!q.empty()){
            auto u=q.front();
            q.pop();
            vis[u]=0;
            for(int v=1;v<=m;v++){
                if(dis[v]>dis[u]+w[u][v]){
                    dis[v]=dis[u]+w[u][v];
                    pre[v]=u;
                    if(!vis[v])q.push(v),vis[v]=1;
                }
            }
        }
        int id=-1;
        for(int i=1;i<=m;i++){
            if(lim[i]&&(id==-1||dis[i]<dis[id]))id=i;
        }
        if(id==-1)break;// 没有增广路了
        lim[id]--;
        ans+=dis[id];// 找到最小费用增广路径
        while(id){// 更新s
            int v=s[pre[id]][id].begin()->second;
            del(v);
            add(v,id);
            id=pre[id];
        }
    }
    cout<<ans<<"\n";
}

AGC018Coins ​

有x+y+zx+y+z个人，第ii个人有AiA_i个金币，BiB_i个银币,CiC_i个铜币

可以分别选择x,y,zx,y,z个人拿金银铜,求最多拿几个牌

那么，左边nn个点，右边33个点，直接跑费用流会超时，因此模拟费用流即可(最大费用，边取反即可)

思路：对a,b排序，那么对于每个ai，他能匹配的都是一个b的前缀

建出费用流模型后，发现他本质上是个反悔贪心，对于当前的aia_i要么顶掉之前的a，要么和未匹配的b匹配

关于行和列的二分图匹配问题 ​

这类问题通常和二分图最大匹配有关

P6931 [ICPC 2017 WF] Mission Improbable ​

n*m的地方摆放着正方体箱子，ai,ja_{i,j}表示这个区域的箱子数量

需要拿走尽可能的箱子，三视图不变

对于俯视图，如果这个位置有箱子，那么可以拿走只剩一个箱子

对于侧视和正视，我们算出行和列的最大值，把箱子摆回去对应的高度

但是还可以节省，如果ii行最大值和jj列最大值相同，那么只用摆一个高度即可

相当于是行和列的匹配，二分图求一个最大匹配

cpp
int vis[210],match[210],ts;
int a[110][110],L[110],R[110];
vector<int> adj[210];
bool find(int u){
    if(vis[u]==ts)return false;
    vis[u]=ts;
    for(auto v:adj[u]){
        if(!match[v]||find(match[v])){
            match[v]=u;
            return true;
        }
    }
    return false;
}
void solve() {
    int n,m;
    cin>>n>>m;
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j])ans+=a[i][j]-1;
            L[i]=max(L[i],a[i][j]);
            R[j]=max(R[j],a[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        if(L[i])ans-=L[i]-1;
    }
    for(int i=1;i<=m;i++){
        if(R[i])ans-=R[i]-1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(L[i]==R[j]&&a[i][j]){
                adj[i].push_back(j+n);
            }
        }
    }
    for(int i=1;i<=n;i++){
        ts++;
        if(find(i))ans+=L[i]-1;
    }
    cout<<ans<<"\n";
}

P2825 [HEOI2016/TJOI2016] 游戏 ​

n*m网格放炸弹，每次会把行和列清空，除非遇到墙，墙会阻止炸弹传播

求最大炸弹数

将行列编号拆分即可，比如**#*，那么赋予**和*为两个不同的行，求二分图最大匹配

Wenwei Lin · 2022 — 2025