网络流基础

~~速通网络流的代价就是忘的巨快~~

总结

网络流中常出现边与点的转化

具体的，拆点以表示点必需的信息，边中插入点以表示边必需的信息

最大流

理论：

$\text{bfs}$ 找 $S$ 到每个点的经过最少边的路径，并对残量网络分层，根据层次反复做 $\text{dfs}$ 每次找到一条增广路并更新

对于每一条从 $x$ 出发并处理完毕的边都不需要重复只用，用 $\text{cur[x]}$ 表示上次处理 $x$ 时遍历的最后一条边($x$ 的当前弧)，每次 $\text{bfs}$ 后都应将 $\text{cur}$ 初始化为 $\text{head}$

尤其在稠密图中效果显著

namespace Webflow{
    inline int bfs(int st,int ed){
        for(rei i=0;i<N;++i) cur[i]=head[i],depth[i]=0;//emmm 这里注意点数不再是n了
        he=1,ta=0; depth[st]=1,que[++ta]=st;
        while(he<=ta){
            rei x=que[he++];
            for(rei i=head[x],y;i;i=Next[i]){
                if(flow[i] && !depth[ y=ver[i] ]){
                    depth[y]=depth[x]+1; que[++ta]=y;
                    if(y==ed) return 1;
                }
            }
        }
        return 0;
    }
    inline int dfs(int x,int T,int left_flow){
        if(!left_flow || x==T) return left_flow;
        rei tmp=0;
        for(rei i=cur[x],y,f;i;i=Next[i]){
            cur[x]=i;
            if(depth[ y=ver[i] ]==depth[x]+1 && (f=dfs(y,T,min(left_flow-tmp,flow[i])))){
                flow[i]-=f; flow[i^1]+=f;
                tmp+=f;
                if(!(left_flow-tmp)) break;
            }
        }
        return tmp;
    }
    inline void Dinic(int S,int T){ maxflow=0; while(bfs(S,T)) maxflow+=dfs(S,T,INF);}
}
}

例题

P2891 [USACO07OPEN]Dining G / P1231 教辅的组成 / P1402 酒店之王

三倍经验的三分图匹配，将两个要匹配 $n1,n2$ 的先分别与源汇点相连，再将用来匹配的一种点 $n$ 拆点以保证只选一次，再读入条件将匹配条件连边

$i:1\rightarrow n1\qquad$ add(S,i,1),add(i,S,0);

$i:1\rightarrow n2\qquad$ add(i+n1,T,1),add(T,i+n1,0);

$i:1\rightarrow n\ \ \qquad$ add(i+n1+n2,i+n+n1+n2,1),add(i+n+n1+n2,i+n1+n2,0);

$u,v\in n1\ \ \qquad$ add(v,u+n1+n2,1),add(u+n1+n2,v,0);

$u,v\in n2\ \ \qquad$ add(u+n+n1+n2,v+n1,1),add(v+n1,u+n+n1+n2,0);

有/无源汇上下界可行/最大流

理论- 无源汇上下界可行流

对于边的上下界 $MAX,MIN$ ，一个简单的想法是整体向下偏移，将下界变为 $0$ ，上界变为 $MAX-MIN$ ，但如此的话并不满足流量守恒

设 $du_i=in_i-out_i$ ，即每个节点的入出之差

当 $du_i=0$ 那么对于该点，流量守恒

当 $du_i>0$ ，从 $S$ 向 $i$ 连一条流量 $du_i$ 的边，当 $du_i<0$ ，从 $i$ 向 $T$ 连一条 $-du_i$ 的边

那么求一次最大流，当所有附加的边均满流时(即，$du_i<=0$) 有可行解

for(rei i=1,u,v,MIN,MAX;i<=m;++i){
    scanf("%d%d%d%d",&u,&v,&MIN,&MAX);
    add(u,v,MAX-MIN,i),add(v,u,0,0);
    du[u]-=MIN,du[v]+=MIN;
    ori[i]=MIN;
}
S=n+1,T=S+1,ori_tot=tot;
for(rei i=1;i<=n;++i){
    if(du[i]>0) add(S,i,du[i],0),add(i,S,0,0);
    else if(du[i]<0) add(i,T,-du[i],0),add(T,i,0,0);
}
Webflow::Dinic(S,T);
bool flag=1;
for(rei i=head[S];i;i=Next[i]) if(flow[i]>0){ flag=0; break;}
if(!flag) return puts("NO"),0;
for(rei i=2;i<=ori_tot;i+=2) ans[ id[i] ]=flow[i^1];//id表示第i条边是原来输入的第几条
puts("YES");
for(rei i=1;i<=m;++i) printf("%d\n",ans[i]+ori[i]);

理论- 有源汇上下界最大流

其实题目的意思是：求一个流使源点总流入等于汇点总流出，其他点满足流量守恒，每条边满足上下界限制，求最大的总流量

~~而不是直接用上界跑最大流，这一定是出题人的语文问题~~

如何转化为无源汇：变成循环流即可，即从源点到汇点建一条流量无限的边

再建超级源点超级汇点，可行流的判断与上题一样

第一次跑的最大流是流满下界的流，图中还剩有 $s\rightarrow t$ 的自由流

那么再删去超级源点汇点以及与之相连的边，再跑 $s\rightarrow t$ 的最大流

答案就是 $流满下界的流+剩下的自由流的最大流$

for(rei i=1,u,v,MIN,MAX;i<=m;++i){
    scanf("%d%d%d%d",&u,&v,&MIN,&MAX);
    add(u,v,MAX-MIN,i),add(v,u,0,0);
    du[u]-=MIN,du[v]+=MIN;
}
S=n+1,T=S+1,ori_tot=tot;
for(rei i=1;i<=n;++i){
    if(du[i]>0) add(S,i,du[i],0),add(i,S,0,0);
    else if(du[i]<0) add(i,T,-du[i],0),add(T,i,0,0);
}
add(t,s,INF,0),add(s,t,0,0);
Webflow::Dinic(S,T);
bool flag=1;
for(rei i=head[S];i;i=Next[i]) if(flow[i]>0){ flag=0; break;}
if(!flag) return puts("please go home to sleep"),0;
ans=flow[ head[t]^1 ]; //跑完最大流后每条边的反向边的流量就为流过该边的流量。求流过t的流量
// printf("%d\n",ans);
for(rei i=1;i<=tot;++i) if(!id[i]) flow[i]=0;//id等于0的边都是与st和ed相连的
head[S]=head[T]=0;
// S=s,T=t;
Webflow::Dinic(s,t);
printf("%d\n",ans+maxflow);

理论- 有源汇上下界最小流

建立超级源点汇点之后跑一次最大流，$t\rightarrow s$ 建一条无限大的边，再跑一次最大流

答案就是无限大的边流过的流量：

由于整个图满足流量平衡，$t$ 的流入等于流出，由于其流出的只有无穷大的边，最小六就是使那条边流过的流量尽量小

ll MIN,MAX;
for(rei i=1,u,v;i<=m;++i){
    scanf("%d%d%lld%lld",&u,&v,&MIN,&MAX);
    add(u,v,MAX-MIN),add(v,u,0);
    du[u]-=MIN,du[v]+=MIN;
}
S=n+1,T=S+1,ori_tot=tot;
for(rei i=1;i<=n;++i){
    if(du[i]>0) add(S,i,du[i]),add(i,S,0);
    else if(du[i]<0) add(i,T,-du[i]),add(T,i,0);
}
Webflow::Dinic(S,T);
add(t,s,INF),add(s,t,0);
Webflow::Dinic(S,T);
bool flag=1;
for(rei i=head[S];i;i=Next[i]) if(flow[i]>0){ flag=0; break;}
if(!flag) return puts("please go home to sleep"),0;
printf("%lld\n",flow[tot]);

最小割

理论

最大流最小割定理：

网络中最大流量等于最小割中割边的容量之和

证略

例题

P4662 [BalticOI 2008]黑手党

void re_dfs(int x){
    vis[x]=1;
    for(rei i=head[x],y;i;i=Next[i]) if(flow[i]>0 && !vis[ y=ver[i] ]) re_dfs(y);
}

int main(){
    scanf("%d%d%d%d",&n,&m,&S,&T);
    T+=n;
    for(rei i=1,x;i<=n;++i) scanf("%d",&x),add(i,i+n,x),add(i+n,i,0);
    for(rei i=1,x,y;i<=m;++i) scanf("%d%d",&x,&y),add(x+n,y,INF),add(y,x+n,0),add(y+n,x,INF),add(x,y+n,0);
    Webflow::Dinic(S,T);
    re_dfs(S);
    for(rei i=2;i<tot;i+=2) if(vis[ ver[i^1] ] && !vis[ ver[i] ]) ans.push_back(ver[i^1]);
    sort(ans.begin(),ans.end());
    for(rei i=0,SS=ans.size()-1;i<=SS;++i) printf("%d%c",ans[i],i==SS ? 10 : 32);
    getchar(),getchar();
    return 0;
}

最大权闭合子图

理论

对于一个有向连通图，每个点带有一个权值，建超级源点汇点，将所有正点权的点连到 $S$ 上，负点权的点连到 $T$ 上，边权为点权的绝对值

特殊的，点权为 $0$ 的点可以被忽略掉，而原图中的边权值设为 $INF$

该图有以下性质：

关于 $S-T$ 的最小割是简单割，即，割集中所有边都与 $S,T$ 相连接
简单割产生的两个子图中，有点 $S$ 的图是闭合图，即，图中任一点的的出边指向的终点仍在该图中
最小割产生的 $图S、图T$ 中，$图S$ 为最大权闭合子图

那么对于有点权的图，求解最大点权的闭合子图步骤为：

记录整个图中所有正点权之和 $sum$
建立流网络，求 $S-T$ 最大流 $maxflow$
最大权闭合子图的权值和即为 $sum-maxflow$

P2805 [NOI2009] 植物大战僵尸

考虑题中的条件得：植物 $i$ 能被攻击当且仅当植物 $i+1$ 与保护 $i$ 的植物都被攻击

与最大权闭合子图中：每个点出边指向的点都属于闭合子图相仿

那么将图转置，所有能被攻击的植物构成一个闭合子图，

同时，注意拓扑判环删去无敌的点

const int N=1100,M=1e6+100;
const int INF=0x3f3f3f3f;
int n,m,S,T;
int que[N],he,ta;
int head[N],ver[M],Next[M],flow[M],cur[M],tot=1,depth[N];
int maxflow,sum;
int vis[N],in[N],score[N];
vector<int> out[N];
queue<int> q;

inline int get_id(int i,int j){ return i*31+j;}

inline void topsort(){
    for(rei i=1;i<=n;++i) for(rei j=1;j<=m;++j){
        rei id=get_id(i,j);
        if(!in[id]) q.push(id),vis[id]=1;
    }
    while(q.size()){
        rei x=q.front(); q.pop();
        for(rei i=0,SS=**out**[x].size()-1;i<=SS;++i){
            rei y=out[x][i];
            --in[y];
            if(!vis[y] && !in[y]) q.push(y),vis[y]=1;
        }
    }
}

int main(){
    // freopen("1.in","r",stdin); freopen("1.ans","w",stdout);
    scanf("%d%d",&n,&m);
    S=N-1,T=N-2;
    for(rei i=1;i<=n;++i) for(rei j=1,w;j<=m;++j){
        scanf("%d%d",&score[ get_id(i,j) ],&w);
        for(rei k=1,r,c;k<=w;++k){
            scanf("%d%d",&r,&c),++r,++c;
            out[ get_id(i,j) ].push_back(get_id(r,c));
            ++in[ get_id(r,c) ];
        }
        if(j<m){
            out[ get_id(i,j+1) ].push_back(get_id(i,j));
            ++in[ get_id(i,j) ];
        }
    }
    topsort();
    for(rei i=1;i<=n;++i) for(rei j=1;j<=m;++j){
        if(!in[ get_id(i,j) ]){
            rei id=get_id(i,j);
            if(!vis[id]) continue;
            if(score[id]>=0){
                add(S,id,score[id]),add(id,S,0);
                sum+=score[id];
                // printf("%d\n",sum);
            }
            else add(id,T,-score[id]),add(T,id,0);
            for(rei k=0,SS=out[id].size()-1;k<=SS;++k){
                rei y=out[id][k];
                if(vis[y]) add(y,id,INF),add(id,y,0);
            }
        }
    }
    Webflow::Dinic(S,T);
    // printf("%lld %lld %lld\n",sum,maxflow,sum-maxflow);
    printf("%d\n",sum-maxflow);
    getchar(),getchar();
    return 0;
}

P4174 [NOI2006] 最大获利 / CF1082G Petya and Graph

int main(){
    scanf("%d%d",&n,&m); S=n+m+1,T=S+1;
    for(rei i=1,p;i<=n;++i) scanf("%d",&p),add(i,T,p),add(T,i,0);//投入连T
    for(rei i=1,a,b,c;i<=m;++i){
        scanf("%d%d%d",&a,&b,&c); sum+=c;
        add(S,n+i,c),add(n+i,S,0);//S连收益
        add(n+i,a,INF),add(a,n+i,0);
        add(n+i,b,INF),add(b,n+i,0);//中间的边不能被删去
    }
    Webflow::Dinic(S,T);
    printf("%lld\n",sum-maxflow);
    getchar(),getchar();
    return 0;
}

P3749 [六省联考2017]寿司餐厅

$n$ 种寿司，每种的类型为 $a_i$ ，吃了第 $i\sim j$ 种寿司会获得 $d_{i,j}$ 的收益，吃了 $c$ 种类型为 $x$ 的寿司会付出 $mx^2+cx$ 的代价，最大化收益与代价差

考虑如何建模：对于每个 $d_{i,j}$ 都看成一种物品，那么选择 $d_{i,j}$ 的条件是已经选择 $d_{i,j+1},d_{i-1,j}$

对于付出的代价，转化为吃每种类型 $x$ 的寿司需付出 $x$ 的代价，吃过类型 $x$ 的寿司需付出 $mx^2$ 的代价

那么选择 $d_{i,i}$ 即表示吃掉第 $i$ 种寿司，需要付出 $a_i$ 的代价，以及 $m\times a_i^2$ 的代价，即，将每个类型也看成物品，选择收益 $d_{i,i}$ 的条件是选择类型 $a_i$

int main(){
    scanf("%d%d",&n,&m);
    for(rei i=1;i<=n;++i) scanf("%d",&a[i]),MAX=max(MAX,a[i]);
    S=0,T=N-1;
    for(rei i=1;i<=n;++i) for(rei j=i;j<=n;++j) scanf("%d",&f[i][j]),id[i][j]=++cnt;
    for(rei i=1;i<=n;++i) for(rei j=i;j<=n;++j){
        rei cost=f[i][j];
        if(i==j){
            if(m) Webflow::add(id[i][j],a[i]+cnt,INF);
            cost-=a[i];
        }
        else{
            Webflow::add(id[i][j],id[i+1][j],INF);
            Webflow::add(id[i][j],id[i][j-1],INF);
        }
        if(cost>0) Webflow::add(S,id[i][j],cost),ans+=cost;
        else if(cost<0) Webflow::add(id[i][j],T,-cost);
    }
    if(m) for(rei i=1;i<=MAX;++i) Webflow::add(++cnt,T,i*i);
    Webflow::Dinic(S,T);
    printf("%lld\n",ans-maxflow);
    getchar(),getchar();
    return 0;
}

P3731 [HAOI2017]新型城市化

$n$ 个城市，存在一些合作 $(x,y)$ ,对于两两都在合作的一些城市称为城市群，保证当前情况下只有最多两个城市群。选出两个之前不合作的城市并使其合作，要求最大城市群大小至少比之前的大 $1$

求所有满足该条件的两两城市

一个很显然的想法是建反图，即，在反图上没有边的点之间存在一条边

那么原图的一个城市群两两有边，对应到反图上两两无边，即对应反图的一个独立集，又由于原图最多两个群，那么反图即是一个二分图

问题转化为，求如何删去反图上一条边使反图的独立集变大

不难有：二分图最大独立集 $=$ 总点数 $-$ 最小点覆盖，其中最小点覆盖 $=$ 二分图最大匹配

那么转化为哪些边必定出现在二分图最大匹配中

那么求最大流后对残量网络缩点，必定有的边即是满流且两点不在同一连通块内的点

证明显然，即，若在同一连通块内则一定有另一匹配边可以替换

注意在 $\text{tarjan}$ 缩点的过程中不去缩满流的边，即 if(!flow[i]) continue;

int main(){
    scanf("%d%d",&n,&m);
    for(rei i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
    for(rei i=1;i<=n;++i) if(!col[i]) paint(i,2);
    S=0,T=n+1;
    for(rei i=1;i<=n;++i){
        if(col[i]==2){ Webflow::add(S,i,1); for(auto v:G[i]) Webflow::add(i,v,1);}
        else Webflow::add(i,T,1);
    }
    Webflow::Dinic(S,T);
    for(rei i=S;i<=T;++i) if(!low[i]) tarjan(i);
    for(rei x=1;x<=n;++x) if(col[x]==2)
        for(rei i=head[x];i;i=Next[i]){
            rei y=ver[i]; if(flow[i] || y==S || y==T) continue;
            if(scc[x]!=scc[y]) ans.push_back(x<y ? mk(x,y) : mk(y,x));
        }
    sort(ans.begin(),ans.end());
    printf("%d\n",ans.size());
    for(auto x:ans) printf("%d %d\n",x.first,x.second);
    getchar(),getchar();
    return 0;
}

最小割树

最小割树- P4123 [CQOI2016]不同的最小割

给定 $n$ 个点的无向连通图，对于其中所有点对的最小割容量，一共能得到 $\frac{n\times (n-1)}{2}$ 个数，求有多少互不相同的

对于一个最小割，它会将图分为两个连通块，联想到树上删边后整棵树分为两个连通块

那么若将最小割视为一条边，那么可以考虑将最小割之间的关系用树表示，即：

对于树上任意两个相邻节点 $S,T$ ，确保删去树上的边 $(S,T)$ 后两个不连通点集与原图上执行 $S,T$ 的最小割之后两个不连通点集的点的分布情况相同，且使边 $(S,T)$ 的边权为最小割

为了满足树的情况，所以需要至少 $n-1$ 个点满足上述条件，此时，对于路径 $(u,v)$ ，枚举路径上的每一条边，最小割即是边权最小的边的权值

那么用 set 维护一下个数，size 即是所求

注意建边的时候建双向边且权值均为 val

int vis[N],p[N];
set<int> s;

void dfs(int x){
    vis[x]=1;
    for(rei i=head[x];i;i=Next[i]){
        rei y=ver[i];
        if(!vis[y] && flow[i]) dfs(y);
    }
}

inline void clear(){ memcpy(flow,ori_flow,sizeof flow); memset(vis,0,sizeof vis);}

inline void solve(int ss,int tt){
    clear(); maxflow=0;
    Webflow::Dinic(ss,tt);
    s.insert(maxflow);
    dfs(ss);
}

int main(){
    scanf("%d%d",&n,&m);
    for(rei i=1,u,v,w;i<=m;++i) scanf("%d%d%d",&u,&v,&w),Webflow::add(u,v,w);
    for(rei i=2;i<=n;++i) p[i]=1;
    for(rei i=2;i<=n;++i){
        S=i,T=p[i];
        solve(S,T);
        for(rei j=i;j<=n;++j) if(p[j]==T && vis[j]) p[j]=S;
    }
    printf("%d\n",s.size());
    getchar(),getchar();
    return 0;
}

P3329 [ZJOI2011]最小割

最小割树的经典应用

分治暴力更新点对答案即可

注意 dfs 的时候需要传参而不是直接用全局的 T qwq

#include <bits/stdc++.h>
#define rei register int
using namespace std;

const int N=210,M=4e4+100;
const int INF=0x3f3f3f3f;
int n,m;
int que[N],he,ta;
int head[N],Next[M],ver[M],cur[N],tot=1,depth[N],flow[M],ori_flow[M];
int vis[N],p[N],ans[N][N],node[N];

namespace Webflow{
    inline void add(int u,int v,int val){
        ver[++tot]=v,Next[tot]=head[u],head[u]=tot; flow[tot]=ori_flow[tot]=val;
        ver[++tot]=u,Next[tot]=head[v],head[v]=tot; flow[tot]=ori_flow[tot]=val;
    }
    inline int bfs(int st,int ed){
        for(rei i=0;i<N;++i) cur[i]=head[i],depth[i]=0;
        he=1,ta=0; depth[st]=1,que[++ta]=st;
        while(he<=ta){
            rei x=que[he++];
            for(rei i=head[x],y;i;i=Next[i]){
                if(flow[i] && !depth[ y=ver[i] ]){
                    depth[y]=depth[x]+1; que[++ta]=y;
                    if(y==ed) return 1;
                }
            }
        }
        return 0;
    }
    int dfs(int x,int T,int left_flow){
        if(!left_flow || x==T) return left_flow;
        rei tmp=0;
        for(rei i=cur[x],y,f;i;i=Next[i]){
            cur[x]=i;
            if(depth[ y=ver[i] ]==depth[x]+1 && (f=dfs(y,T,min(left_flow-tmp,flow[i])))){
                flow[i]-=f,flow[i^1]+=f;
                tmp+=f;
                if(!(left_flow-tmp)) break;
            }
        }
        return tmp;
    }
    inline int Dinic(int S,int T,int res=0){ while(bfs(S,T)) res+=dfs(S,T,INF); return res;}
}

void dfs(int x){
    vis[x]=1;
    for(rei i=head[x];i;i=Next[i]){
        rei y=ver[i];
        if(!vis[y] && flow[i]) dfs(y);
    }
}

inline void clear(){ memcpy(flow,ori_flow,sizeof flow); memset(vis,0,sizeof vis);}
inline void init(){
    memset(head,0,sizeof head); tot=1; memset(flow,0,sizeof flow); memset(ori_flow,0,sizeof ori_flow); memset(ver,0,sizeof ver); memset(Next,0,sizeof Next);
    memset(ans,0x3f,sizeof ans);
    for(rei i=1;i<=n;++i) node[i]=i;
}

void solve(int l,int r){
    if(l==r) return ;
    clear();
    int t[2][N]={0};
    rei tmp=Webflow::Dinic(node[l],node[r]);
    dfs(node[l]);
    for(rei i=1;i<=n;++i) if(vis[i])
        for(rei j=1;j<=n;++j) if(!vis[j])
            ans[i][j]=ans[j][i]=min(ans[i][j],tmp);
    for(rei i=l;i<=r;++i) t[ vis[node[i]] ][ ++t[vis[node[i]]][0] ]=node[i];
    for(rei i=l,j=1;j<=t[0][0];++j,++i) node[i]=t[0][j];
    for(rei i=l+t[0][0],j=1;j<=t[1][0];++j,++i) node[i]=t[1][j];
    solve(l,l+t[0][0]-1),solve(l+t[0][0],r);
}

int main(){
    rei T; scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        init();
        for(rei i=1,u,v,w;i<=m;++i) scanf("%d%d%d",&u,&v,&w),Webflow::add(u,v,w);
        solve(1,n);
        rei q; scanf("%d",&q);
        for(rei k=1,x;k<=q;++k){
            scanf("%d",&x);
            rei res=0;
            for(rei i=1;i<=n;++i) for(rei j=i+1;j<=n;++j) if(ans[i][j]<=x) ++res;
            printf("%d\n",res);
        }
        puts("");
    }
    getchar(),getchar();
    return 0;
}

P4897 【模板】最小割树（Gomory-Hu Tree）

比上面的更简单，对于询问 u v 直接输出 ans[u][v] 即可

UVA11594 All Pairs Maximum Flow

板子，输出所有 ans 即可，注意特判 i=j 时输出 0

~~好吧其实这全是板子题，因为没考过所以有懒狗不去练其他的题了qwq~~

ZKW费用流

板子

namespace ZKW{
    bool flag=0;
    bool SPFA(int S,int T,int n){
        memset(dis,INF,sizeof dis); memset(vis,0,sizeof vis); memset(level,0,sizeof level);
        //dis维护到终点最短距离，level分层图
        dis[S]=0,level[S]=1,vis[S]=true;
        deque<int> q; q.push_back(S);//SLF 优化
        while(q.size()){
            rei x=q.front(); q.pop_front(); vis[x]=0;
            for(rei i=head[x],y;i;i=Next[i]){
                if(dis[ y=ver[i] ]>dis[x]+cost[i] && flow[i]>0){
                    dis[y]=dis[x]+cost[i];
                    level[y]=level[x]+1;
                    if(!vis[y]){
                        vis[y]=1;
                        (q.size() && dis[y]<dis[ q.front() ]) ? q.push_front(y) : q.push_back(y);
                    }
                }
            }
        }
        return dis[T]!=dis[n+1];
    }
    int dfs(int x,int T,int t,ll &fflow,ll &ccost){
        if(x==T) return fflow+=t,flag=1,t;
        rei num=0,newflow=0;
        for(rei i=head[x],y;i;i=Next[i]){
            if(t==num) break;
            if(dis[x]+cost[i]==dis[ y=ver[i] ] && level[x]+1==level[y] && flow[i]>0){
                newflow=dfs(y,T,min(t-num,flow[i]),fflow,ccost);
                num+=newflow; ccost+=newflow*cost[i];
                flow[i]-=newflow; flow[i^1]+=newflow;
            }
        }
        return num;
    }
    void costflow(int S,int T,int n){
        while(SPFA(S,T,n)){
            flag=1;
            while(flag){
                flag=0;
                dfs(S,T,INF,maxflow,mincost);
            }
        }
    }
}

P4452 [国家集训队]航班安排

$K$ 架飞机，$N$ 个机场，$M$ 个要求，请求在 $s$ 时刻从 $a$ 起飞，$t$ 时刻降落到 $b$ ，获利 $c$ ，求总收益最大

最大费用最大流，存负边权即可

考虑建模对象：点或请求

以点来建边的话需要对时间讨论，不如选择请求建边，可以处理请求与请求的关系

对于源点

判断从起始点 $1$ 是否能直达请求的起点，建流量 $INF$ ，费用 $w_{1,qa}$，有

if(q[i].s>=t[1][ q[i].a ]) add(Fake_S,i,INF,w[1][ q[i].a ]),add(i,Fake_S,0,-w[1][ q[i].a ]);

由于 $k$ 架飞机，再建真正的源点，向 $1$ 连边，流量 $k$ 费用 $0$

add(S,Fake_S,k,0),add(Fake_S,S,0,0);
对于汇点

判断请求结束后能不能再规定时间内回到 $1$ ，有

if(q[i].t+t[ q[i].b ][1]<=tim) add(i+m,T,INF,w[ q[i].b ][1]),add(T,i+m,0,-w[ q[i].b ][1]);
请求的转移

对于每个请求的结束地 $qi_b$，枚举所有的请求，找是否有从结束点 $qi_a$ 赶到起始点 $qj_a$ 后能赶上的情况

for(rei j=1;j<=m;++j) if(i!=j && q[i].t+t[ q[i].b ][ q[j].a ]<=q[j].s) add(i+m,j,INF,w[ q[i].b ][ q[j].a ]),add(j,i+m,0,-w[ q[i].b ][ q[j].a ]);
注意每个请求只能进行一次

套路的对进行请求拆点，流量设为 $1$

add(i,i+m,1,-q[i].c),add(i+m,i,0,q[i].c);

S=0,T=2*m+2,Fake_S=T-1;
for(rei i=1;i<=n;++i) for(rei j=1;j<=n;++j) scanf("%d",&t[i][j]);
for(rei i=1;i<=n;++i) for(rei j=1;j<=n;++j) scanf("%d",&w[i][j]);
for(rei i=1;i<=m;++i) scanf("%d%d%d%d%d",&q[i].a,&q[i].b,&q[i].s,&q[i].t,&q[i].c),++q[i].a,++q[i].b;
for(rei i=1;i<=m;++i){
    add(i,i+m,1,-q[i].c),add(i+m,i,0,q[i].c);//拆点，控制只能由一次收益
    if(q[i].t+t[ q[i].b ][1]<=tim) add(i+m,T,INF,w[ q[i].b ][1]),add(T,i+m,0,-w[ q[i].b ][1]);
    // else continue;
    if(q[i].s>=t[1][ q[i].a ]) add(Fake_S,i,INF,w[1][ q[i].a ]),add(i,Fake_S,0,-w[1][ q[i].a ]);
    for(rei j=1;j<=m;++j) if(i!=j && q[i].t+t[ q[i].b ][ q[j].a ]<=q[j].s) add(i+m,j,INF,w[ q[i].b ][ q[j].a ]),add(j,i+m,0,-w[ q[i].b ][ q[j].a ]);
}
add(S,Fake_S,k,0),add(Fake_S,S,0,0);
ZKW::costflow();

P2604 [ZJOI2010]网络扩容

一张有向图，边有容量与扩容费用 $w$，其中 $w$ 表示将容量扩大 $1$ 所需的费用，求不扩容情况下 $1$ 到 $n$ 的最大流，以及最大流增加 $k$ 的最小扩容费用

对于第一问，显然跑费用为 $0$ 的费用流即可

考虑第二问需要的增加 $k$ ，有一个很好的 $\text{trick}$ 是：对于原汇点 $T$ ，建 $TT$ ，并连 $T\rightarrow TT$ ，其容量设为 $maxflow+k$ ，费用为 $0$

int main(){
    scanf("%d%d%d",&n,&m,&k); S=1,T=n; TT=n+1;
    for(rei i=1;i<=m;++i){
        scanf("%d%d%d%d",&U[i],&V[i],&cap[i],&val[i]);
        ZKW::add(U[i],V[i],cap[i],0);
    }
    ZKW::costflow(S,T,n);
    printf("%lld ",maxflow);
    clear();
    for(rei i=1;i<=m;++i){
        ZKW::add(U[i],V[i],cap[i],0);
        ZKW::add(U[i],V[i],INF,val[i]);
    }
    ZKW::add(T,TT,maxflow+k,0);
    maxflow=0,mincost=0;
    ZKW::costflow(S,TT,n+1);
    printf("%lld\n",mincost);
    getchar(),getchar();
    return 0;
}

神奇的建模

P3308 [SDOI2014]LIS

给定序列 $A$ ，对于 $A_i$ 有删除代价 $b_i$ 和附加值 $c_i$ ，删除若干项使 $A$ 的最长上升子序列长度减少至少 $1$ ，且付出代价之和最小并输出方案。对于多种方案，输出按删去项附加值大小排序后字典序最小的情况

一个思路是：用一个流量表示一个 $\text{LIS}$

设 $dp_i$ 表示以 $i$ 为结尾的最长上升子序列长度，那么显然位置 $i$ 在 $\text{LIS}$ 中只能位于第 $dp_i$ 个位置，即 $\text{LIS}$ 的下标序列 $pos$ 一定满足 $dp_{pos_i}=i$

对于所有满足 $i<j$ 且 $dp_i=dp_j-1$ 的位置连 $i\rightarrow j$ ，设 $\text{LIS}$ 长度为 $len$ ，那么任意一条 $\text{LIS}$ 可被表示为路径 $dp_s=1 \Rightarrow dp_t=len$ ，那么要破坏所有这种路径

那么显然可以拆点，并将边流量设为 $b_i$ ，那么最小割即为最小破坏代价
对于 $dp_i=1$ ，连 $S\rightarrow i$ ，对于 $dp_j=len$ ，连 $j\rightarrow T$
对于所有满足 $i<j 且 dp_i=dp_j-1$ ，连 $i\rightarrow j$ ，流量为 $INF$ ，即不可破坏该路径

那么 $S\rightarrow T$ 的最小割即为最小代价

对于附加值大小，对 $c$ 数组排序，考虑每条边能否成为割边，即，从该点的入点能否不通过流量为 $0$ 的点到达出点，用 bfs 即可

强制使其为割边，将所有边复原后，将其与反向边流量均置为 $0$ ，再跑 $S\rightarrow T$ 最小割得到新图的最小割

int a[N],dp[N],MAX,b[N];
struct node{
    int val,id;
    friend bool operator <(const node &a,const node &b){ return a.val<b.val;}
}c[N];

inline void clear(){
    memset(head,0,sizeof head),memset(ver,0,sizeof ver),memset(Next,0,sizeof Next),memset(flow,0,sizeof flow);
    tot=1; MAX=0;
}

signed main(){
    rei TT; scanf("%lld",&TT);
    while(TT--){
        clear();
        scanf("%lld",&n); S=0,T=(n<<1)+1;
        for(rei i=1;i<=n;++i) scanf("%lld",&a[i]);
        for(rei i=1;i<=n;++i){
            dp[i]=1;
            for(rei j=1;j<i;++j) if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1);
            MAX=max(MAX,dp[i]);
        }
        for(rei i=1,x;i<=n;++i) scanf("%lld",&x),Webflow::add(i,i+n,x);
        for(rei i=1;i<=n;++i){
            if(dp[i]==1) Webflow::add(S,i,INF);
            if(dp[i]==MAX) Webflow::add(i+n,T,INF);
            for(rei j=i+1;j<=n;++j) if(a[i]<a[j] && dp[j]==dp[i]+1) Webflow::add(i+n,j,INF);
        }
        for(rei i=1,x;i<=n;++i) scanf("%lld",&x),c[i]=(node){x,i};
        sort(c+1,c+1+n);
        maxflow=Webflow::Dinic(S,T);
        rei num=0;
        for(rei i=1;i<=n;++i){
            rei x=c[i].id,y=x+n;
            if(!Webflow::bfs(x,y)){
                b[++num]=x,flow[x<<1]=flow[(x<<1)+1]=0;
                for(rei i=2;i<=tot;i+=2) flow[i]+=flow[i^1],flow[i^1]=0;
                while(Webflow::bfs(S,T)) Webflow::dfs(S,T,INF);
            }
        }
        sort(b+1,b+1+num);
        printf("%lld %lld\n",maxflow,num);
        for(rei i=1;i<=num;++i) printf("%lld%c",b[i],i==num ? 10 : 32);
    }
    getchar(),getchar();
    return 0;
}

P5458 [BJOI2016]水晶

题面好长不写了

自然的想法是将三维点 $(x,y,z)$ 用二维的 $(x-z,y-z)$ 表示，不难发现这样符合题面，具体的，用 map 维护点编号

要求剩余总合最大显然求最小割，并拿总价值减去

对于一个能量源，对其周围的六个点黑白染色，形成共振当且仅当相邻的黑点白点能量源点均存在

那么每个点进行拆点，相邻的三类点之间用 $INF$ 连接，最小割即可

inline int get_mod(int x){ return ((X[x]+Y[x])%3+3)%3;}
int main(){
    S=0,T=N-1;
    scanf("%d",&n);
    for(rei i=1,v;i<=n;++i){
        scanf("%d%d%d%d",&X[i],&Y[i],&Z[i],&v); X[i]-=Z[i],Y[i]-=Z[i];
        v=((X[i]+Y[i])%3+3)%3 ? v*10 : v*11;
        ans+=v;
        if(!mp[ mk(X[i],Y[i]) ]) mp[ mk(X[i],Y[i]) ]=++mp_cnt;
        val[ mp[ mk(X[i],Y[i]) ] ]+=v;
    }
    for(rei i=1;i<=n;++i){
        rei now=mp[ mk(X[i],Y[i]) ];
        if(vis[now]) continue;
        vis[now]=1;
        Webflow::add(now,now+n,val[now]);
        if(get_mod(i)==1) Webflow::add(S,now,INF);
        else if(get_mod(i)==2) Webflow::add(now+n,T,INF);
        else{
            rei tmp_s,tmp_t;
            tmp_s=mp[ mk(X[i]-1,Y[i]-1) ]; if(tmp_s) Webflow::add(tmp_s+n,now,INF);
            tmp_s=mp[ mk(X[i]+1,Y[i]) ]; if(tmp_s) Webflow::add(tmp_s+n,now,INF);
            tmp_s=mp[ mk(X[i],Y[i]+1) ]; if(tmp_s) Webflow::add(tmp_s+n,now,INF);
            tmp_t=mp[ mk(X[i]+1,Y[i]+1)]; if(tmp_t) Webflow::add(now+n,tmp_t,INF);
            tmp_t=mp[ mk(X[i]-1,Y[i]) ]; if(tmp_t) Webflow::add(now+n,tmp_t,INF);
            tmp_t=mp[ mk(X[i],Y[i]-1) ]; if(tmp_t) Webflow::add(now+n,tmp_t,INF);
        }
    }
    ans-=Webflow::Dinic(S,T);
    printf("%.1lf\n",(double) ans/10.0);
    getchar(),getchar();
    return 0;
}