很久之前就想要学习网络流了，最近也刚学了网络流，于是便有了本篇博客。
关于算法：
网络流模板
个人喜欢用dinic跑非一次性建边的网络流，用isap跑一次性建边的网络流，用zkw跑费用流，至于HLPP我还不会
当然网络流还是要靠建图。
网络流24题：（仅包含部分题目）
P2756 飞行员配对方案问题
显然的一个二分图匹配问题，还要输出方案；
我们考虑建图，首先一个飞行员只能匹配一个飞行员，所以我们从S向一类飞行员连边，从另一类飞行员向T连边，边权为1，然后对于能匹配的飞行员我们连接1或者inf的边（本体都可），完成建图。
关于输出方案：考虑残量网络上的反向边发生流量改变即可。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;
#define I inline
#define R register
#define inf 1073742823
#define FOR(i,begin,end) for(R int i=begin;i<=end;++i)
#define ROF(i,begin,end) for(R int i=begin;i>=end;--i)
#include<queue>
namespace IO{
char buf[1<<21],*pa=buf,*pb=buf;
char buffer[1<<21];int p1=-1;const int p2=(1<<21)-1;
I char gc(){return pa==pb&&(pb=(pa=buf)+fread(buf,1,1<<21,stdin),pa==pb)?EOF:*pa++;}
template<class T>I void read(T &x){
x=0;R int y=0;R char ch=gc();
for(;!isdigit(ch);ch=gc())y=ch=='-';
for(;isdigit(ch);ch=gc())x=x*10+(ch^48);
(y)&&(x=-x);return;}
I void flush(){fwrite(buffer,1,p1+1,stdout);p1=-1;return;}
I void pc(int ch){if(p1==p2)flush();buffer[++p1]=ch;return;}
template<class T>I void write(T x){
static char buf[20];static int len =-1;
if(x>=0){do buf[++len]=(x%10)^48,x/=10;while(x);}
else{pc('-');do buf[++len]=(-(x%10))^48,x/=10;while(x);}
while(len>=0)pc(buf[len--]);
return;}
}
using namespace IO;
int tot,s,t;
const int maxn = 50000+50;
const int maxm = 200000+200;
#define ci const int &
struct edge{
int u,v,f,n;
I edge(ci uu =0,ci vv=0,ci ff=0,ci nn=0):u(uu),v(vv),f(ff),n(nn){}
}e[maxm];
int cnt=1,head[maxn],cur[maxn],gap[maxn],dis[maxn],mxflow=0;
I void add(ci u,ci v,ci f){
e[++cnt]=edge(u,v,f,head[u]),head[u]=cnt;
e[++cnt]=edge(v,u,0,head[v]),head[v]=cnt;
}
I void bfs(){
queue<int>q;q.push(t),gap[dis[t]=1]++;
while(!q.empty()){
int u=q.front();q.pop();
for(int ee=head[u],v;v=e[ee].v,ee;ee=e[ee].n)
if(!dis[v])gap[dis[v]=dis[u]+1]++,q.push(v);
}
}
int dfs(ci u,ci flow){
if(u==t&&((mxflow+=flow)||1))return flow;
int us=0,f;
for(int ee=cur[u],v;cur[u]=ee,v=e[ee].v,ee;ee=e[ee].n)
if(dis[v]==dis[u]-1){
if(f=dfs(v,min(flow-us,e[ee].f)))
e[ee].f-=f,e[ee^1].f+=f,us+=f;
if(us==flow)return flow;
}
(--gap[dis[u]])?(++gap[++dis[u]]):dis[s]=tot+1;
return us;
}
I int isap(){
bfs();
while(dis[s]<=tot+1)
memcpy(cur,head,sizeof head),
dfs(s,inf);
return mxflow;
}
int n,m;
int fa[maxn];
I int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);}
I void output(int x){
write(x),pc(' ');
for(int ee=head[x],v;v=e[ee].v,ee;ee=e[ee].n)
if(ee>=4*n+2)
if(e[ee^1].f!=0&&v>n)
output(v-n);
return;
}
signed main(){
int x,y;
read(n),read(m);
s=0,t=2*n+1,tot=2*n+2;
FOR(i,1,n)
add(s,i,1),
add(i+n,t,1);
// cnt = 4n+1;
FOR(i,1,m)
read(x),read(y),
add(x,y+n,1);
// cnt = 4n + 2m + 1;
int ans = n - isap();
FOR(i,1,n)fa[i]=i;
for(int ee=4*n+2;ee<=cnt;ee+=2)
if(e[ee^1].f!=0)
fa[getf(e[ee].v-n)]=getf(e[ee].u);
FOR(i,1,n)
if(getf(i)==i)
output(i),pc('\n');
write(ans);
flush();
return 0;
}
P3254 圆桌问题
仍然是一个类似二分图的问题，也要输出方案。
我们考虑从S向每个单位连接流量为的边，表示这个单位的人数，从每个餐桌向T连接流量为的边，表示餐桌可以容纳的人数，对于所有的单位向所有的餐桌连一条流量为1的边，表示同一个单位来的代表不在同一个餐桌就餐,建图完成。输出方案与上题同理。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <vector>
using namespace std;
#define I inline
#define R register
#define inf 1073742823
#define FOR(i,begin,end) for(R int i=begin;i<=end;++i)
#define ROF(i,begin,end) for(R int i=begin;i>=end;--i)
#include<queue>
namespace IO{
char buf[1<<21],*pa=buf,*pb=buf;
char buffer[1<<21];int p1=-1;const int p2=(1<<21)-1;
I char gc(){return pa==pb&&(pb=(pa=buf)+fread(buf,1,1<<21,stdin),pa==pb)?EOF:*pa++;}
template<class T>I void read(T &x){
x=0;R int y=0;R char ch=gc();
for(;!isdigit(ch);ch=gc())y=ch=='-';
for(;isdigit(ch);ch=gc())x=x*10+(ch^48);
(y)&&(x=-x);return;}
I void flush(){fwrite(buffer,1,p1+1,stdout);p1=-1;return;}
I void pc(int ch){if(p1==p2)flush();buffer[++p1]=ch;return;}
template<class T>I void write(T x){
static char buf[20];static int len =-1;
if(x>=0){do buf[++len]=(x%10)^48,x/=10;while(x);}
else{pc('-');do buf[++len]=(-(x%10))^48,x/=10;while(x);}
while(len>=0)pc(buf[len--]);
return;}
}
using namespace IO;
int s,t,tot;
const int maxn = 50000+50;
const int maxm = 200000+200;
#define ci const int &
struct edge{
int u,v,f,n;
I edge(ci uu =0,ci vv=0,ci ff=0,ci nn=0):u(uu),v(vv),f(ff),n(nn){}
}e[maxm];
int cnt=1,head[maxn],cur[maxn],gap[maxn],dis[maxn],mxflow=0;
I void add(ci u,ci v,ci f){
e[++cnt]=edge(u,v,f,head[u]),head[u]=cnt;
e[++cnt]=edge(v,u,0,head[v]),head[v]=cnt;
}
I void bfs(){
queue<int>q;q.push(t),gap[dis[t]=1]++;
while(!q.empty()){
int u=q.front();q.pop();
for(int ee=head[u],v;v=e[ee].v,ee;ee=e[ee].n)
if(!dis[v])gap[dis[v]=dis[u]+1]++,q.push(v);
}
}
int dfs(ci u,ci flow){
if(u==t&&((mxflow+=flow)||1))return flow;
int us=0,f;
for(int ee=cur[u],v;cur[u]=ee,v=e[ee].v,ee;ee=e[ee].n)
if(dis[v]==dis[u]-1){
if(f=dfs(v,min(flow-us,e[ee].f)))
e[ee].f-=f,e[ee^1].f+=f,us+=f;
if(us==flow)return flow;
}
(--gap[dis[u]])?(++gap[++dis[u]]):dis[s]=tot+1;
return us;
}
int n,m,x,sum;
int rr[maxn],cc[maxn];
vector<int>ans[maxn];
signed main(){
read(n),read(m);
s=0,t=n+m+1;
tot=t;
FOR(i,1,n)
read(rr[i]),sum+=rr[i],
add(s,i,rr[i]);
FOR(i,1,m)
read(cc[i]),
add(i+n,t,cc[i]);
FOR(i,1,n)
FOR(j,1,m)
add(i,j+n,1);
while(dis[s]<=tot+1)memcpy(cur,head,sizeof(head)),dfs(s,inf);
if(mxflow!=sum){
puts("0");
return 0;
}
write(1),pc('\n');
for(int ee=2*(n+m+1);ee<=cnt;ee+=2)
if(e[ee^1].f!=0)
ans[e[ee].u].push_back(e[ee].v);
FOR(i,1,n){
for(auto k:ans[i])
write(k-n),pc(' ');
pc('\n');
}
flush();
return 0;
}
P2764 最小路径覆盖问题
题目渐渐有了难度，模板题洛谷也给了提示
我们考虑拆点，把一个点拆成两个点，第一个拆点表示出边，第二个拆点表示入边，我们把S向第一个拆点连一条流量为1的边，表示这个点的出度最大为1，把第二个拆点向T连接一条流量为1的边,表示这个点的最大入度为1，然后我们连接原图中的边，流量为1，表示存在路径，建图完成。
我们对原图跑一个最大流，显然就是匹配数，所以n-匹配数即为答案，关于路径输出和路径起点，与第一题同理。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;
#define I inline
#define R register
#define inf 1073742823
#define FOR(i,begin,end) for(R int i=begin;i<=end;++i)
#define ROF(i,begin,end) for(R int i=begin;i>=end;--i)
#include<queue>
namespace IO{
char buf[1<<21],*pa=buf,*pb=buf;
char buffer[1<<21];int p1=-1;const int p2=(1<<21)-1;
I char gc(){return pa==pb&&(pb=(pa=buf)+fread(buf,1,1<<21,stdin),pa==pb)?EOF:*pa++;}
template<class T>I void read(T &x){
x=0;R int y=0;R char ch=gc();
for(;!isdigit(ch);ch=gc())y=ch=='-';
for(;isdigit(ch);ch=gc())x=x*10+(ch^48);
(y)&&(x=-x);return;}
I void flush(){fwrite(buffer,1,p1+1,stdout);p1=-1;return;}
I void pc(int ch){if(p1==p2)flush();buffer[++p1]=ch;return;}
template<class T>I void write(T x){
static char buf[20];static int len =-1;
if(x>=0){do buf[++len]=(x%10)^48,x/=10;while(x);}
else{pc('-');do buf[++len]=(-(x%10))^48,x/=10;while(x);}
while(len>=0)pc(buf[len--]);
return;}
}
using namespace IO;
int tot,s,t;
const int maxn = 50000+50;
const int maxm = 200000+200;
#define ci const int &
struct edge{
int u,v,f,n;
I edge(ci uu =0,ci vv=0,ci ff=0,ci nn=0):u(uu),v(vv),f(ff),n(nn){}
}e[maxm];
int cnt=1,head[maxn],cur[maxn],gap[maxn],dis[maxn],mxflow=0;
I void add(ci u,ci v,ci f){
e[++cnt]=edge(u,v,f,head[u]),head[u]=cnt;
e[++cnt]=edge(v,u,0,head[v]),head[v]=cnt;
}
I void bfs(){
queue<int>q;q.push(t),gap[dis[t]=1]++;
while(!q.empty()){
int u=q.front();q.pop();
for(int ee=head[u],v;v=e[ee].v,ee;ee=e[ee].n)
if(!dis[v])gap[dis[v]=dis[u]+1]++,q.push(v);
}
}
int dfs(ci u,ci flow){
if(u==t&&((mxflow+=flow)||1))return flow;
int us=0,f;
for(int ee=cur[u],v;cur[u]=ee,v=e[ee].v,ee;ee=e[ee].n)
if(dis[v]==dis[u]-1){
if(f=dfs(v,min(flow-us,e[ee].f)))
e[ee].f-=f,e[ee^1].f+=f,us+=f;
if(us==flow)return flow;
}
(--gap[dis[u]])?(++gap[++dis[u]]):dis[s]=tot+1;
return us;
}
I int isap(){
bfs();
while(dis[s]<=tot+1)
memcpy(cur,head,sizeof head),
dfs(s,inf);
return mxflow;
}
int n,m;
int fa[maxn];
I int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);}
I void output(int x){
write(x),pc(' ');
for(int ee=head[x],v;v=e[ee].v,ee;ee=e[ee].n)
if(ee>=4*n+2)
if(e[ee^1].f!=0&&v>n)
output(v-n);
return;
}
signed main(){
int x,y;
read(n),read(m);
s=0,t=2*n+1,tot=2*n+2;
FOR(i,1,n)
add(s,i,1),
add(i+n,t,1);
// cnt = 4n+1;
FOR(i,1,m)
read(x),read(y),
add(x,y+n,1);
// cnt = 4n + 2m + 1;
int ans = n - isap();
FOR(i,1,n)fa[i]=i;
for(int ee=4*n+2;ee<=cnt;ee+=2)
if(e[ee^1].f!=0)
fa[getf(e[ee].v-n)]=getf(e[ee].u);
FOR(i,1,n)
if(getf(i)==i)
output(i),pc('\n');
write(ans);
flush();
return 0;
}
P2765 魔术球问题
显然这是一个需要不断加边的网络流，我们将一个数向与他组成完全平方数的数的拆点连边，S向原数连边，拆点向T连边，跑网络流即可，与上一题思想相似。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;
#define I inline
#define R register
#define inf 1073742823
#define FOR(i,begin,end) for(R int i=begin;i<=end;++i)
#define ROF(i,begin,end) for(R int i=begin;i>=end;--i)
namespace IO{
char buf[1<<21],*pa=buf,*pb=buf;
char buffer[1<<21];int p1=-1;const int p2=(1<<21)-1;
I char gc(){return pa==pb&&(pb=(pa=buf)+fread(buf,1,1<<21,stdin),pa==pb)?EOF:*pa++;}
template<class T>I void read(T &x){
x=0;R int y=0;R char ch=gc();
for(;!isdigit(ch);ch=gc())y=ch=='-';
for(;isdigit(ch);ch=gc())x=x*10+(ch^48);
(y)&&(x=-x);return;}
I void flush(){fwrite(buffer,1,p1+1,stdout);p1=-1;return;}
I void pc(int ch){if(p1==p2)flush();buffer[++p1]=ch;return;}
template<class T>I void write(T x){
static char buf[20];static int len =-1;
if(x>=0){do buf[++len]=(x%10)^48,x/=10;while(x);}
else{pc('-');do buf[++len]=(-(x%10))^48,x/=10;while(x);}
while(len>=0)pc(buf[len--]);
return;}
}
using namespace IO;
const int maxn = 50000+50;
const int maxm = 200000+200;
#define Ci const int &
int n,m,s,t;
struct edge{
int u,v,n,flow;
I edge(Ci _u=0,Ci _v=0,Ci _n=0,Ci _flow=0):u(_u),v(_v),n(_n),flow(_flow){}
}e[maxm];
int cnt=1,head[maxn],cur[maxn];
I void add(Ci u,Ci v,Ci flow){
e[++cnt]=edge(u,v,head[u],flow),head[u]=cnt;
e[++cnt]=edge(v,u,head[v],0),head[v]=cnt;
}
int dep[maxn],pre[maxn];
#include<queue>
I bool bfs(){
queue<int>q;
memset(dep,0,sizeof dep);
memcpy(cur,head,sizeof(head));
dep[s]=1,q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
for(int ee=head[u],v;v=e[ee].v,ee;ee=e[ee].n)
if(e[ee].flow&&dep[v]==0)
dep[v]=dep[u]+1,q.push(v);
}
return dep[t];
}
int dfs(int u,int limit){
if(limit==0||u==t)return limit;
int flow=0,f;
for(int ee=cur[u],v;cur[u]=ee,v=e[ee].v,ee;ee=e[ee].n)
if(dep[v]==dep[u]+1&&(f=dfs(v,min(limit,e[ee].flow)))){
flow+=f;
limit-=f;
e[ee].flow-=f;
e[ee^1].flow+=f;
pre[u>>1]=v>>1;
if(!limit)break;
}
return flow;
}
I int dinic(){
int ans=0;
while(bfs())
ans+=dfs(s,inf);
return ans;
}
I bool check(int x){
int xx=sqrt(x);
return xx==x;
}
int top,now,sta[maxn],vis[maxn];
signed main(){
read(n);
s=maxn-10,t=maxn-9;
while(top<=n){
++now;
add(s,now<<1,1);
add((now<<1)|1,t,1);
for(int i=sqrt(now)+1;i*i<(now<<1);++i)
add((i*i-now)<<1,(now << 1)|1,1);
int flow=dinic();
if(!flow)
sta[++top]=now;
}
write(now-1),pc('\n');
FOR(i,1,n)
if(!vis[sta[i]]){
for(int u=sta[i];u&&u!=(t>>1);u=pre[u])
vis[u]=1,write(u),pc(' ');
pc('\n');
}
flush();
return 0;
}
P2766 最长不下降子序列问题
第一问我们考虑直接DP；
第二问我们向原点和拆点连一条为1的边表示只能被选一次，然后对于DP值等于1的从源点S向其连边，流量为1，对于DP等于长度的，从其向汇点T连边，流量为1，表示路径可行性。
第三问在残量网络上加源点到1的边，假如最后一个数在最长上升子序列上，连接一条向汇点的边，还有原点向拆点连边，流量为inf，表示可以无限使用。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;
#define I inline
#define R register
#define inf 1073742823
#define FOR(i,begin,end) for(R int i=begin;i<=end;++i)
#define ROF(i,begin,end) for(R int i=begin;i>=end;--i)
#include<queue>
namespace IO{
char buf[1<<21],*pa=buf,*pb=buf;
char buffer[1<<21];int p1=-1;const int p2=(1<<21)-1;
I char gc(){return pa==pb&&(pb=(pa=buf)+fread(buf,1,1<<21,stdin),pa==pb)?EOF:*pa++;}
template<class T>I void read(T &x){
x=0;R int y=0;R char ch=gc();
for(;!isdigit(ch);ch=gc())y=ch=='-';
for(;isdigit(ch);ch=gc())x=x*10+(ch^48);
(y)&&(x=-x);return;}
I void flush(){fwrite(buffer,1,p1+1,stdout);p1=-1;return;}
I void pc(int ch){if(p1==p2)flush();buffer[++p1]=ch;return;}
template<class T>I void write(T x){
static char buf[20];static int len =-1;
if(x>=0){do buf[++len]=(x%10)^48,x/=10;while(x);}
else{pc('-');do buf[++len]=(-(x%10))^48,x/=10;while(x);}
while(len>=0)pc(buf[len--]);
return;}
}
using namespace IO;
int tot,s,t;
const int maxn = 5000+50;
const int maxm = 200000+200;
#define ci const int &
struct edge{
int u,v,f,n;
I edge(ci uu =0,ci vv=0,ci ff=0,ci nn=0):u(uu),v(vv),f(ff),n(nn){}
}e[maxm];
int cnt=1,head[maxn],cur[maxn],gap[maxn],dis[maxn];
I void add(ci u,ci v,ci f){
e[++cnt]=edge(u,v,f,head[u]),head[u]=cnt;
e[++cnt]=edge(v,u,0,head[v]),head[v]=cnt;
}
I void bfs(){
memset(dis,0,sizeof dis);
memset(gap,0,sizeof gap);
queue<int>q;q.push(t),gap[dis[t]=1]++;
while(!q.empty()){
int u=q.front();q.pop();
for(int ee=head[u],v;v=e[ee].v,ee;ee=e[ee].n)
if(!dis[v])gap[dis[v]=dis[u]+1]++,q.push(v);
}
}
int dfs(ci u,ci flow){
if(u==t)return flow;
int us=0,f;
for(int ee=cur[u],v;cur[u]=ee,v=e[ee].v,ee;ee=e[ee].n)
if(dis[v]==dis[u]-1){
if(f=dfs(v,min(flow-us,e[ee].f)))
e[ee].f-=f,e[ee^1].f+=f,us+=f;
if(us==flow)return flow;
}
(--gap[dis[u]])?(++gap[++dis[u]]):dis[s]=tot+1;
return us;
}
I int isap(){
int ans=0;
bfs();
while(dis[s]<=tot+1)
memcpy(cur,head,sizeof head),
ans+=dfs(s,inf);
return ans;
}
int n,a[maxn],dp[maxn];
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
signed main(){
read(n);
FOR(i,1,n)read(a[i]),dp[i]=1;
FOR(i,1,n)
FOR(j,1,i-1)
if(a[j]<=a[i])dp[i]=max(dp[i],dp[j]+1);
int len;FOR(i,1,n)len=max(len,dp[i]);
write(len),pc('\n');
s=0,t=1;tot=2+2*n;
FOR(i,1,n)if(dp[i]==1)add(s,ls(i),1);
FOR(i,1,n)if(dp[i]==len)add(rs(i),t,1);
FOR(i,1,n)add(ls(i),rs(i),1);
FOR(i,1,n)
FOR(j,1,i-1)
if(a[j]<=a[i]&&dp[j]+1==dp[i])
add(rs(j),ls(i),1);
int last;
write(last=isap()),pc('\n');
add(ls(1),rs(1),inf),add(s,ls(1),inf);
if(dp[n]==len)add(ls(n),rs(n),inf),add(rs(n),t,inf);
write(last+isap()),pc('\n');
flush();
return 0;
}
P2762 太空飞行计划问题
最大权闭合图问题，考虑如下建图方案，由源点S向每个实验仪器连边，流量为费用，由实验向汇点T连边，流量为获利，由实验仪器向对应的实验连边，流量为inf，对所建图求最小割，即最小割为ans，则最后答案为总实验的获利-ans；
（若割边是源点到仪器则表示仪器不选用，若割边为实验则代表实验不选用）
P1251 餐巾计划问题
(之前写的忘了保存挂了，我哭了，嘤嘤嘤)
我们考虑如下建图方式
将每一天拆为两个点，分别表示旧餐巾和新餐巾。
（消耗=产生=r）（不特别说明，费用为零，流量为inf）
由源点向每天的旧餐巾连接一条流量为产生的边，表示每天产生的旧餐巾。
由每天的新餐巾向汇点连接一条流量为消耗的边，表示每天消耗的新餐巾。
由源点向每天的新餐巾连接一条费用的p的边，表示每天购买的新餐巾。
由每天的旧餐巾向时间加m/n处的新餐巾连接一条费用为f/s的边，表示快/慢洗的餐巾。
这样建图我们保证了，最大流一定为每天消耗的新餐巾的总和，最小费用即为最小花费。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <queue>
#define int long long
using namespace std;
#define I inline
#define R register
#define inf 2147483647
#define FOR(i,begin,end) for(R int i=begin;i<=end;++i)
#define ROF(i,begin,end) for(R int i=begin;i>=end;--i)
namespace IO{
char buf[1<<21],*pa=buf,*pb=buf;
char buffer[1<<21];int p1=-1;const int p2=(1<<21)-1;
I char gc(){return pa==pb&&(pb=(pa=buf)+fread(buf,1,1<<21,stdin),pa==pb)?EOF:*pa++;}
template<class T>I void read(T &x){
x=0;R int y=0;R char ch=gc();
for(;!isdigit(ch);ch=gc())y=ch=='-';
for(;isdigit(ch);ch=gc())x=x*10+(ch^48);
(y)&&(x=-x);return;}
I void flush(){fwrite(buffer,1,p1+1,stdout);p1=-1;return;}
I void pc(int ch){if(p1==p2)flush();buffer[++p1]=ch;return;}
template<class T>I void write(T x){
static char buf[20];static int len =-1;
if(x>=0){do buf[++len]=(x%10)^48,x/=10;while(x);}
else{pc('-');do buf[++len]=(-(x%10))^48,x/=10;while(x);}
while(len>=0)pc(buf[len--]);
return;}
}
using namespace IO;
const int maxn = 50000+500;
const int maxm = 200000+2000;
#define ci const int &
struct edge{
int u,v,f,w,n;
I edge(ci uu=0,ci vv=0,ci ff=0,ci ww=0,ci nn=0):u(uu),v(vv),f(ff),w(ww),n(nn){}
}e[maxm];
int dis[maxn],vis[maxn],cur[maxn],head[maxn],cnt=1,n,m,s,t;
int cost=0,flow=0;
I void add(ci u,ci v,ci f,ci w){
e[++cnt]=edge(u,v,f,w,head[u]),head[u]=cnt;
e[++cnt]=edge(v,u,0,-w,head[v]),head[v]=cnt;
}
I bool spfa(ci s,ci t){
memset(vis,0,sizeof vis);
memset(dis,0x3f,sizeof dis);
deque<int>q;q.push_front(t);
vis[t]=1,dis[t]=0;
while(!q.empty()){
int u=q.front();q.pop_front();
for(int ee=head[u],v;v=e[ee].v,ee;ee=e[ee].n)
if(e[ee^1].f>0&&dis[v]>dis[u]-e[ee].w){
dis[v]=dis[u]-e[ee].w;
if(!vis[v])vis[v]=1,(!q.empty()&&dis[q.front()]>dis[v])?
q.push_front(v):
q.push_back(v);
}
vis[u]=0;
}
return dis[s]==0x3f3f3f3f3f3f3f3f?0:1;
}
int dfs(ci u,ci ff){
if(u==t)return vis[t]=1,ff;
int us=0,f;vis[u]=1;
for(int ee=cur[u],v;cur[u]=ee,v=e[ee].v,ee;ee=e[ee].n)
if(vis[v]==0&&e[ee].f>0&&dis[u]-e[ee].w==dis[v]){
if((f=dfs(v,min(e[ee].f,ff-us)))>0)
cost+=f*e[ee].w,e[ee].f-=f,e[ee^1].f+=f,us+=f;
if(us==ff)break;
}
return us;
}
I void cost_flow(){
while(spfa(s,t)){
vis[t]=1;
while(vis[t]){
memcpy(cur,head,sizeof head);
memset(vis,0,sizeof vis);
flow+=dfs(s,inf);
}
}
}
int r[maxn];
#define ls(o) (o<<1)
#define rs(o) (o<<1|1)
signed main(){
read(n);
int p,t1,c1,t2,c2;
s=rs(0),t=ls(n+2);
FOR(i,1,n)
read(r[i]),add(s,ls(i),r[i],0),add(rs(i),t,r[i],0);
read(p),read(t1),read(c1),read(t2),read(c2);
FOR(i,1,n){
add(s,rs(i),inf,p);
if(i+1<=n)add(ls(i),ls(i+1),inf,0);
if(i+t1<=n)add(ls(i),rs(i+t1),inf,c1);
if(i+t2<=n)add(ls(i),rs(i+t2),inf,c2);
}
cost_flow();
write(cost);
flush();
return 0;
}
###P4013 数字梯形问题
我们考虑拆点控制流量，然后就没了。
还有无法在残量网络上继续加边跑最小费用。
洛谷好像不给数据，然后手写了一个数据生成。
第一问：
我们把拆点和原点连接一条流量为1（表次数限制），费用为-点值（表示费用），然后按照题意连边即可。
第二问：
将第一问拆点和原点的连边流量改为inf（表无次数限制）。
同时需要注意最下边一行的点，连接汇点T的边流量也要改为inf。
第三问：
除了源点向第一行的点的连边流量为1外，其他的流量为inf（表无次数限制）
#include <bits/stdc++.h>
using namespace std;
#define I inline
#define R register
#define inf 1073742823
#define FOR(i,begin,end) for(R int i=begin;i<=end;++i)
#define ROF(i,begin,end) for(R int i=begin;i>=end;--i)
namespace IO{
char buf[1<<21],*pa=buf,*pb=buf;
char buffer[1<<21];int p1=-1;const int p2=(1<<21)-1;
I char gc(){return pa==pb&&(pb=(pa=buf)+fread(buf,1,1<<21,stdin),pa==pb)?EOF:*pa++;}
template<class T>I void read(T &x){
x=0;R int y=0;R char ch=gc();
for(;!isdigit(ch);ch=gc())y=ch=='-';
for(;isdigit(ch);ch=gc())x=(x<<3)+(x<<1)+(ch^48);
(y)&&(x=-x);return;}
I void flush(){fwrite(buffer,1,p1+1,stdout);p1=-1;return;}
I void pc(int ch){if(p1==p2)flush();buffer[++p1]=ch;return;}
template<class T>I void write(T x){
static char buf[20];static int len =-1;
if(x>=0){do buf[++len]=(x%10)^48,x/=10;while(x);}
else{pc('-');do buf[++len]=(-(x%10))^48,x/=10;while(x);}
while(len>=0)pc(buf[len--]);
return;}
}
using namespace IO;
int main(){
srand(GetTickCount());
int n=10,m=2;
write(m),pc(' '),write(n),pc('\n');
FOR(i,m,m+n-1)
{
FOR(j,1,i)write(rand()%100),pc(' ');
pc('\n');
}
flush();
return 0;
}
题目的代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <queue>
using namespace std;
#define I inline
#define R register
#define inf 1073742823
#define FOR(i,begin,end) for(R int i=begin;i<=end;++i)
#define ROF(i,begin,end) for(R int i=begin;i>=end;--i)
namespace IO{
char buf[1<<21],*pa=buf,*pb=buf;
char buffer[1<<21];int p1=-1;const int p2=(1<<21)-1;
I char gc(){return pa==pb&&(pb=(pa=buf)+fread(buf,1,1<<21,stdin),pa==pb)?EOF:*pa++;}
template<class T>I void read(T &x){
x=0;R int y=0;R char ch=gc();
for(;!isdigit(ch);ch=gc())y=ch=='-';
for(;isdigit(ch);ch=gc())x=x*10+(ch^48);
(y)&&(x=-x);return;}
I void flush(){fwrite(buffer,1,p1+1,stdout);p1=-1;return;}
I void pc(int ch){if(p1==p2)flush();buffer[++p1]=ch;return;}
template<class T>I void write(T x){
static char buf[20];static int len =-1;
if(x>=0){do buf[++len]=(x%10)^48,x/=10;while(x);}
else{pc('-');do buf[++len]=(-(x%10))^48,x/=10;while(x);}
while(len>=0)pc(buf[len--]);
return;}
}
using namespace IO;
const int maxn = 50000+500;
const int maxm = 2000000+2000;
#define ci const int &
struct edge{
int u,v,f,w,n;
I edge(ci uu=0,ci vv=0,ci ff=0,ci ww=0,ci nn=0):u(uu),v(vv),f(ff),w(ww),n(nn){}
}e[maxm];
int dis[maxn],vis[maxn],cur[maxn],head[maxn],cnt=1,n,m,s,t;
int cost=0,flow=0;
I void add(ci u,ci v,ci f,ci w){
e[++cnt]=edge(u,v,f,w,head[u]),head[u]=cnt;
e[++cnt]=edge(v,u,0,-w,head[v]),head[v]=cnt;
}
I bool spfa(ci s,ci t){
memset(vis,0,sizeof vis);
memset(dis,0x3f,sizeof dis);
deque<int>q;q.push_front(t);
vis[t]=1,dis[t]=0;
while(!q.empty()){
int u=q.front();q.pop_front();
for(int ee=head[u],v;v=e[ee].v,ee;ee=e[ee].n)
if(e[ee^1].f>0&&dis[v]>dis[u]-e[ee].w){
dis[v]=dis[u]-e[ee].w;
if(!vis[v])vis[v]=1,(!q.empty()&&dis[q.front()]>dis[v])?
q.push_front(v):
q.push_back(v);
}
vis[u]=0;
}
return dis[s]==0x3f3f3f3f?0:1;
}
int dfs(ci u,ci ff){
if(u==t)return vis[t]=1,ff;
int us=0,f;vis[u]=1;
for(int ee=cur[u],v;cur[u]=ee,v=e[ee].v,ee;ee=e[ee].n)
if(vis[v]==0&&e[ee].f>0&&dis[u]-e[ee].w==dis[v]){
if((f=dfs(v,min(e[ee].f,ff-us)))>0)
cost+=f*e[ee].w,e[ee].f-=f,e[ee^1].f+=f,us+=f;
if(us==ff)break;
}
return us;
}
I void cost_flow(){
while(spfa(s,t)){
vis[t]=1;
while(vis[t]){
memcpy(cur,head,sizeof head);
memset(vis,0,sizeof vis);
flow+=dfs(s,inf);
}
}
}
I void clear(){
memset(head,0,sizeof head);
memset(e,0,sizeof e);
cnt=1;cost=0,flow=0;
}
#define ls(o) (o<<1)
#define rs(o) (o<<1|1)
int a[50][50],id[50][50];
signed main(){
s=ls(0),t=rs(0);
int tot=0;
read(m),read(n);
FOR(i,m,m+n-1)
FOR(j,1,i)
read(a[i][j]),id[i][j]=++tot;
// work 1
FOR(i,1,m)
add(s,ls(id[m][i]),1,0);
FOR(i,m,m+n-1)
FOR(j,1,i)
add(ls(id[i][j]),rs(id[i][j]),1,-a[i][j]);
FOR(i,m,m+n-2)
FOR(j,1,i)
add(rs(id[i][j]),ls(id[i+1][j]),1,0),
add(rs(id[i][j]),ls(id[i+1][j+1]),1,0);
FOR(i,1,m+n-1)
add(rs(id[m+n-1][i]),t,1,0);
cost_flow();
write(-cost),pc('\n');
// work 2
clear();
FOR(i,1,m)
add(s,ls(id[m][i]),1,0);
FOR(i,m,m+n-1)
FOR(j,1,i)
add(ls(id[i][j]),rs(id[i][j]),inf,-a[i][j]);
FOR(i,m,m+n-2)
FOR(j,1,i)
add(rs(id[i][j]),ls(id[i+1][j]),1,0),
add(rs(id[i][j]),ls(id[i+1][j+1]),1,0);
FOR(i,1,m+n-1)
add(rs(id[m+n-1][i]),t,1,0);
cost_flow();
write(-cost),pc('\n');
// work 3
clear();
FOR(i,1,m)
add(s,ls(id[m][i]),1,0);
FOR(i,m,m+n-1)
FOR(j,1,i)
add(ls(id[i][j]),rs(id[i][j]),inf,-a[i][j]);
FOR(i,m,m+n-2)
FOR(j,1,i)
add(rs(id[i][j]),ls(id[i+1][j]),inf,0),
add(rs(id[i][j]),ls(id[i+1][j+1]),inf,0);
FOR(i,1,m+n-1)
add(rs(id[m+n-1][i]),t,inf,0);
cost_flow();
write(-cost),pc('\n');
flush();
return 0;
}
大概本博客就完结了，网络流二十四题的题目连接直接放到下面了：
P1251 餐巾计划问题
P2754 [CTSC1999]家园 / 星际转移问题
P2756 飞行员配对方案问题
P2761 软件补丁问题
P2762 太空飞行计划问题
P2763 试题库问题
P2764 最小路径覆盖问题
P2765 魔术球问题
P2766 最长不下降子序列问题
P2770 航空路线问题
P2774 方格取数问题
P2775 机器人路径规划问题
P3254 圆桌问题
P3355 骑士共存问题
P3356 火星探险问题
[P3357 最长k可重线段集问题]https://www.luogu.com.cn/problem/P3357)
P3358 最长k可重区间集问题
P4009 汽车加油行驶问题
P4011 孤岛营救问题
P4012 深海机器人问题
P4013 数字梯形问题
P4014 分配问题
P4015 运输问题
P4016 负载平衡问题
##当然网络流24题只是比较基础的入门题目，本博客只提供入门方面的参考
