浅谈网络流
本文章同步发表在洛谷博客。
前言
该文为笔者学习网络流后写下的文章，内容较为丰富，涵盖了最大流、费用流和上下界网络流知识，末尾还有各类网络流的配套习题。另外推荐大家去做包含【网络流与线性规划 24 题】标签的网络流题目。
关于本文代码：也许你已经注意到了，某些代码使用的是 vector 存图，而其他代码用的是链式前向星存图。这是因为笔者原是用 vector 存图的，后来发现在网络流算法中，用链式前向星会更方便，逐改变了自己的习惯。可能看起来有些不适，烦请各位多多谅解。不过逻辑都是一样的啦，只是实现方式不同，所以影响应该也不大呀。
如对本文内容有疑惑，欢迎私信询问，我将尽量在三个工作日内答复。文章可能有些瑕疵，如果你发现了，也欢迎在下面评论区中提出，我会尽力修改。
网络模型
想象一些有向水管构成的图，每条水管都有固定的流量上限，有源点可以出水，有汇点可以收水。
形式化描述这个东西。设 \(f_{u \to v}\) 表示 \(u\) 向 \(v\) 流的流量，\(c_{u \to v}\) 表示 \(u \to v\) 这条路上的容量（流量）限制。\(S\) 为源点（起点），\(T\) 为汇点（终点）。
对于边 \(u \to v\) 有 \(w\) 的流量，则 \(f_{u \to v} = w\)，并且 \(f_{v \to u} = -w\) 而非什么 \(f_{v \to u} = 0\)。也许你已经看出来了，这个东西和牛顿第三定律有些类似，负的流量表示反向流动。
问题来了，如何判断一个流是否合法？换句话说，合法流的充要条件是什么？
首先有反对称性，也就是所谓的 \(f_{u \to v} = -f_{v \to u}\)。
接着，流量满足限制，即 \(f_{u \to v} \le c_{u \to v}\)。
以及要满足内部流量守恒。即，对于 \(u \not= S,T\)，有 \(\sum_{x} f_{u \to x} = 0\)。
推论：外部流量守恒 \(\sum_{x} f_{S \to x} = \sum_{y} f_{y \to T}\)，即源点流出量等于汇点流入量。
要求找出一个合法的流所对应的 \(f\)，并最大化 \(\sum_{x} f_{S \to x}\)（源点流出的流量），等价于最大化 \(\sum_{x} f_{x \to T}\)（汇点流入的流量）。
这，称为最大流问题。
这个模型和现实情况还是略有区别的，它允许凭空出现的“环流”。不过在最大流问题中，“环流”不仅不能贡献流量，还浪费了容量，所以并不会对最优解造成任何影响。
残量网络上的调整
记 \(r_{u \to v} = c_{u \to v} - f_{u \to v}\)，即“剩余流量”。称 \(r\) 为残量网络。
残量调整定理：
对于网络 \(c\)，记可能的所有合法流的集合为 \(F_c\)。对于任意一个 \(f_0 \in F_c\)，记 \(r = c - f_0\)（即残量网络），则 \(F_c = f_0 + F_r\)。也就是说，源网络的所有合法流可以在残量网络上调整而获得。
可以直观理解，残量网络上的任意流相当于“不超出容量限制的调整”，相当于在原图上增加流量，也可以把已经流过去的流撤回来。这自然可以得到所有合法的流。
增广路与增广
根据残量调整定理，可以得到一种最大流算法的思路：对于当前网络 \(c\)，求一个流方案 \(f\) 满足 \(\text{flow}(f) > 0\)，然后将 \(c\) 减去 \(f\) 并将最大流答案加上 \(\text{flow}(f)\)。重复这一过程，最大流在不断变大，由于最大流必然是有限的，这个算法必然能结束。
即不断在残量网络上找出一种正的流（调整方法），直到找不到为止。
最终 \(c\) 上不能存在任何正的流，即有容量的边不能联通 \(S,T\)。
我们不妨先考虑最简单的流 \(f\)——一条路径。
于是这里就要引入两个定义：增广路与增广。
- 增广路：找出残量网络 \(r\) 中从 \(S\) 到 \(T\) 的一条路径，其中路径上的 \(r\) 都 \(>0\)，称这条路径为一条增广路。
- 增广：算出增广路中 \(r\) 的最小值 \(x\)，让增广路上的每条边都多流 \(x\) 的流量，这一过程叫做增广。
我们只要不断找出增广路，然后对其进行增广，直到找不出为止，即可得到最大流。
最大流的算法实现
Ford-Fulkerson 算法
简称 FF 算法。
它的做法是，直接用 DFS 找增广路，找到一条就增广。
时间复杂度上界 \(O(m \times \max x)\)，\(\max x\) 表示最大流量。
Edmonds-Karp 算法
简称 EK 算法。
它在 FF 算法的基础上进行了一些改进，只考虑容量为正的边，并改用 BFS 找增广路。
这里有一个最短路单调定理：在 EK 算法不断增广的过程中，源点到各个点的最短路单调不降。根据这个最短路单调定理，可证明 EK 算法的时间复杂度为 \(O(n \times m^2)\)。
Dinic 算法
在 EK 算法的基础上改进，考虑用一次“多路增广”完成原先的“增广路长度保持为 \(L\) 的一系列连续增广”。
首先跑一次 BFS 求出 \(dis_{1 \sim n}\)。有一个性质，那就是只需要考虑在最短路上的边。即对于边 \(u \to v\)，当且仅当 \(dis_v = dis_u + 1\) 时才需要考虑这条边。
用 DFS 进行多路增广。具体地，到达 \(u\) 点，流入流量为 \(f\)，枚举各个出边搜索看看能流出多少。如果能流，将 \(f\) 减去流走的流量，并调整残量网络，尝试下一条边。最后返回总的流出去的流量。
这里有个优化方法叫做当前弧优化。具体地，其为点 \(u\) 记录了 \(p_u\)，表示第 \(1 \sim p_u\) 条出边都已经流不出流量，下次访问该点，枚举从 \(p_u + 1\) 开始。这样，每条边都只有一次尝试失败。
总时间复杂度为 \(O(n^2 \times m)\)，但是如果不加当前弧优化的话，复杂度会退化为 \(O(n^2 \times m^2)\)。
例题选讲
P3163 危桥
首先根据题目中桥的连边进行建图，正常的桥建成的边的流量为 \(+ \infty\)，而危桥的流量限制为 \(2\)，因为题目要求只能经过最多两次。
接着建立源点 \(S\) 和汇点 \(T\)，然后让它们分别对应地去连边。具体地，源点向 \(a_1,b_1\) 分别连流量为 \(a_n,b_n\) 的边，\(a_2,b_2\) 分别向 \(T\) 连 \(a_n,b_n\) 的边。
直接对这个图跑最大流，然后判断最终的流量是否为 \(2 \times (a_n + b_n)\) 就行了……吗？
不！因为你可能往返，危桥不一定只经过了 \(2\) 次。然后这里有一个很厉害的解决办法，我们对这个图反着再跑一次最大流！看它的流量是不是也是 \(2 \times (a_n + b_n)\)。如果它也是，那么往返的问题就不存在了；如果它不是，就说明确实存在往返，危桥发生状况。
反着跑最大流到底是什么东西呢。简单来说，就是把 \(b_1\) 和 \(b_2\) 颠倒了过去，再连边跑最大流。
这里需要跑两次最大流，因此边的信息要维护好，别漏了或重了。
#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 100;
const int INF = 0x3f3f3f3f;
struct line{int to,wei,Db;};
int n,sa,ta,an,sb,tb,bn,St,Ed,dis[N],Ans;
vector<line> g[N],e[N];
queue<int> q;bool flag;
int read(){
int su=0,pp=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
return su*pp;
}
void Add_Edge(int x,int y,int z){
int idx=e[x].size(),idy=e[y].size();
e[x].pb({y,z,idy}),e[y].pb({x,0,idx});return;
}
void Add_Gdge(int x,int y,int z){
int idx=g[x].size(),idy=g[y].size();
g[x].pb({y,z,idy}),g[y].pb({x,0,idx});return;
}
bool BFS_Canit(){
for(int i=1;i<=n+2;i++)dis[i]=0;
while(!q.empty())q.pop();
dis[St]=1,q.push(St);
while(!q.empty()){
int u=q.front();q.pop();
for(auto [v,w,id]:g[u])if(w&&!dis[v])
{dis[v]=dis[u]+1;if(v==Ed)return 1;q.push(v);}
}return 0;
}
int DFS_Cntflow(int u,int flow){
if(u==Ed)return flow;int now=flow;
for(auto &[v,w,id]:g[u])
if(w&&dis[v]==dis[u]+1){
int tmp=DFS_Cntflow(v,min(now,w));
if(!tmp)dis[v]=0;else w-=tmp,g[v][id].wei+=tmp,now-=tmp;
}
return flow-now;
}
int Sol_Dinic(){
int res=0,flow=0;
while(BFS_Canit())
while(flow=DFS_Cntflow(St,INF))res+=flow;
return res;
}
int main(){
while(scanf("%d %d %d %d %d %d %d",&n,&sa,&ta,&an,&sb,&tb,&bn)!=EOF){
sa++,ta++,sb++,tb++;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
char h;cin>>h;
if(h=='O')Add_Edge(i,j,2);
if(h=='N')Add_Edge(i,j,INF);
}
for(int i=1;i<=n;i++)g[i]=e[i];
St=n+1,Ed=n+2,flag=1;
Add_Gdge(St,sa,2*an);Add_Gdge(St,sb,2*bn);
Add_Gdge(ta,Ed,2*an);Add_Gdge(tb,Ed,2*bn);
Ans=Sol_Dinic();if(Ans!=2*(an+bn))flag=0;
for(int i=1;i<=n;i++)g[i]=e[i];
Add_Gdge(St,sa,2*an);Add_Gdge(St,tb,2*bn);
Add_Gdge(ta,Ed,2*an);Add_Gdge(sb,Ed,2*bn);
Ans=Sol_Dinic();if(Ans!=2*(an+bn))flag=0;
if(flag)cout<<"Yes\n";else cout<<"No\n";
for(int i=1;i<=n+2;i++)
g[i].clear(),e[i].clear();
}
return 0;
}
P1231 教辅的组成
考虑对其建网络流的一张图。但是这张图该怎么建呢？
首先考虑让匹配的书与练习册，或者书与答案，进行一个连边。容量限制当然就是 \(1\)。
此时再建立源点 \(S\) 和汇点 \(T\)，让 \(S\) 连练习册，\(T\) 连答案，接着从 \(S\) 出发向 \(T\) 跑最大流。
这样就结束了吗？不！这样跑，你会发现一个很严重的事情，那就是在这里，一本书你可能对应上了多本练习册或者答案。这样的事情是不允许的，虽然题目说这个人大致知道对应关系，但这也仅仅是可能的对应关系而已。一本书不可能对应两本练习册或者两本答案，但是题目中可能给定的一本书连向了多本练习册或者答案。
那这个东西该怎么改进呢？有一个很绝的法子——拆点。怎么说？就是把书给拆成两个点。本来我们的书是只有一个点的，现在我们给拆成两个，一个连练习册们，一个连答案们，然后再把它俩连起来。容量？限制为 \(1\)！这就是核心——你限制了容量是 \(1\)，那么不管你左右连了多少分叉，你都只能抓出一个匹配上，不然这里就过不去，那这个流方案就不合法了。
于是这样你就可以解决该问题了，拆点的时候有些小细节要注意一下。
#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 5e4+5;
const int INF = 0x3f3f3f3f;
struct line{int to,wei,Db;};
int n1,n2,n3,mm,St,Ed,dis[N];
vector<line> g[N];queue<int> q;
int read(){
int su=0,pp=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
return su*pp;
}
int ID(int p,int x){
if(p==1)return x;
if(p==2)return n2+x;
if(p==3)return n1+n2+x;
if(p==4)return n1+n1+n2+x;
}
void Add_edge(int x,int y,int z){
int idx=g[x].size(),idy=g[y].size();
g[x].pb({y,z,idy}),g[y].pb({x,0,idx});return;
}
bool BFS_Canit(){
for(int i=1;i<=Ed;i++)dis[i]=0;
while(!q.empty())q.pop();
dis[St]=1,q.push(St);
while(!q.empty()){
int u=q.front();q.pop();
for(auto [v,w,id]:g[u])if(w&&!dis[v])
{dis[v]=dis[u]+1;if(v==Ed)return 1;q.push(v);}
}return 0;
}
int DFS_Cntflow(int u,int flow){
if(u==Ed)return flow;int now=flow;
for(auto &[v,w,id]:g[u]){
if(now<=0)break;
if(w&&dis[v]==dis[u]+1){
int tmp=DFS_Cntflow(v,min(now,w));
if(!tmp)dis[v]=0;else w-=tmp,g[v][id].wei+=tmp,now-=tmp;
}
}return flow-now;
}
int Sol_Dinic(){
int res=0,flow=0;
while(BFS_Canit())
while(flow=DFS_Cntflow(St,INF))res+=flow;
return res;
}
int main(){
n1=read(),n2=read(),n3=read();
mm=read();
while(mm--){
int x=read(),y=read();
Add_edge(ID(1,y),ID(2,x),1);
}mm=read();
while(mm--){
int x=read(),y=read();
Add_edge(ID(3,x),ID(4,y),1);
}for(int i=1;i<=n1;i++)
Add_edge(ID(2,i),ID(3,i),1);
St=n1+n1+n2+n3+1,Ed=n1+n1+n2+n3+2;
for(int i=1;i<=n2;i++)
Add_edge(St,ID(1,i),1);
for(int i=1;i<=n3;i++)
Add_edge(ID(4,i),Ed,1);
cout<<Sol_Dinic()<<"\n";
return 0;
}
P2763 试题库问题
这道题目显然可以用最大流来做，难点在于如何建图。
首先建立源点和汇点，源点与试题相连，汇点与类型相连，对应试题与对应类型相连。
接下来考虑边的容量：因为一道题只能有一个，所以源点和试题连的边容量为 \(1\)；同理一道题只能满足一种类型，所以试题和类型连的边的容量也为 \(1\)；而需要满足的类型是有多个的，所以类型与汇点连的边的容量为所需类型的数量。
建完图直接跑最大流就可以了，统计方案只需找到没有被割掉的边输出即可。
#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 2005;
const int Inf = 0x3f3f3f3f;
struct line{int to,wei,Db;};
int n,k,sum,St,Ed,dis[N];
vector<line> g[N];queue<int> q;
int read(){
int su=0,pp=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
return su*pp;
}
void Add_edge(int x,int y,int z){
int idx=g[x].size(),idy=g[y].size();
g[x].pb({y,z,idy}),g[y].pb({x,0,idx}); return;
}
bool BFS_Canit(){
for(int i=1;i<=n+k+2;i++)dis[i]=0;
while(!q.empty())q.pop();
dis[St]=1,q.push(St);
while(!q.empty()){
int u=q.front();q.pop()
for(auto [v,w,id]:g[u])
if(w&&!dis[v])
dis[v]=dis[u]+1;
if(v==Ed)return 1;
q.push(v);
}
}return 0;
}
int DFS_Cntflow(int u,int flow){
if(u==Ed)return flow;
int now=flow;
for(auto &[v,w,id]:g[u])
if(w&&dis[v]==dis[u]+1){
int tmp=DFS_Cntflow(v,min(now,w));
if(!tmp)dis[v]=0;
else w-=tmp,g[v][id].wei+=tmp,now-=tmp;
}
return flow-now;
}
int Sol_Dinic(){
int res=0,flow=0;
while(BFS_Canit())
while(flow=DFS_Cntflow(St,Inf))res+=flow;
return res;
}
int main(){
k=read(),n=read();
St=n+k+1,Ed=St+1;
for(int i=1;i<=k;i++){int w=read();sum+=w;Add_edge(n+i,Ed,w);}
for(int i=1;i<=n;i++){
Add_edge(St,i,1);int cnt=read();
while(cnt--){int x=read();Add_edge(i,x+n,1);}
}if(Sol_Dinic()==sum){
for(int i=1;i<=k;i++){
cout<<i<<":";
for(auto [j,w,id]:g[n+i])
if(w&&j<=n)cout<<" "<<j;
cout<<"\n";
}
}else cout<<"No Solution!\n";
return 0;
}
费用流模型
现在自来水公司要为水管收费了。对于一条 \(u \to v\) 的水管，其费用记为 \(l_{u \to v}\)，表示每通过该水管运送 \(1\) 单位流量，就要收费 \(l_{u \to v}\)。在最大化流量的前提下，还要使得总费用最小，这就是费用流的模型。
费用具有反对称性，即 \(l_{u \to v} = - l_{v \to u}\)。对于一条边上的流量，撤回的费用是相反数。
有一个定理：求得同流量中最小费用的流，当且仅当残量网络中不存在负环（费用和为负数的环）。
简单证明一下。首先有充分性，若存在负环，在这个负环上流一圈，流量不变费用减小。以及有必要性，记残缺网络为 \(r\)，据残量调整定理，若当前流不是最小费用流，一定存在 \(f \in F_r\) 满足 \(\text{flow}(f) = 0\)，而 \(f\) 没有外来流量，只是由多个环流叠加而成。每次从 \(f\) 中找出一个环流，如果是非负环，就把它从 \(f\) 中删掉，这样 \(\text{cost}(f)\) 不会变大。重复这个过程，最终一定能找到负环。
费用流的算法实现
SSP 算法
每次找出残量网络上 \(S \to T\) 的最短路进行增广。
这里又有一个定理：若初始图中无负环，SSP 算法的增广过程中，残量网络上不会产生负环。
证明过于复杂，就不写了。
好吧证明还是要写的喵！
假设在某次增广后第一次出现负环，则负环必然与增广路有交。记交集为 \(a \leadsto b\)，增广路为 \(S \leadsto a \leadsto b \leadsto T\)，负环为 \(b \leadsto a \leadsto_2 b\)。根据负环有 $\text{cost}(b \leadsto a) + \text{cost}(a \leadsto_2 b) <0 $，又有 \(\text{cost}(b \leadsto a) = -\text{cost}(a \leadsto b)\)，故 \(\text{cost}(a \leadsto b) > \text{cost}(a \leadsto_2 b)\)。可以构造出更短增广路 \(S \leadsto a \leadsto_2 b \leadsto T\)，矛盾。
推论：SSP 算法最终求得的是最小费用最大流。
SSP 算法是求解费用流的主干思想，其中的关键步骤是最短路的求解。根据求最短路的方法不同，产生了多个子算法。
Edmonds-Karp 算法
EK 算法是每次增广用 SPFA 求解最短路。
EK 算法是伪多项式复杂度的（没有关于 \(n,m\) 的多项式上界），受到费用的引导，在构造数据中的表现不会比 FF 算法高明。
但它是竞赛实践中最常用的费用流算法。和 Dinic 算法跑不满的情况类似，大多数题目中，使用 EK 算法就已经足够了。
例题选讲
P2045 方格取数加强版
考虑如何建模。
首先将一个方格 \((i,j)\) 转化为两个点，一个入点，一个出点。从每个入点向对应的出点连两条边，一条容量为 \(1\)，费用为格子里的数值，还有一条容量为 \(k-1\)，费用为 \(0\)。
还有，从 \((i,j)\) 的出点向 \((i+1,j)\) 和 \((i,j+1)\) 的入点各连一条边，容量为 \(k\)，费用为 \(0\)。
最后让 \((1,1)\) 的入点为源点，\((n,n)\) 的出点为汇点，跑最大费用最大流即可。
#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 2e5+5;
const int INF = 0x3f3f3f3f;
int n,k,St,Ed,dis[N],f[N],ps[N];
int tot=1,head[N],to[N],wei[N],cst[N],nxt[N];
bool vis[N];queue<int> q;
int read(){
int su=0,pp=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
return su*pp;
}
void Add_edge(int x,int y,int z,int w){
to[++tot]=y,wei[tot]=z,cst[tot]=w;
nxt[tot]=head[x],head[x]=tot;
to[++tot]=x,wei[tot]=0,cst[tot]=-w;
nxt[tot]=head[y],head[y]=tot;return;
}
int Num(int x,int y,int k){return (x-1)*n+y+k*n*n;}
bool SPFA_Canit(){
while(!q.empty())q.pop();
memset(dis,-0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(St),dis[St]=0,vis[St]=1,f[St]=INF;
while(!q.empty()){
int u=q.front();vis[u]=0;q.pop();
for(int i=head[u];i;i=nxt[i]){
if(!wei[i])continue;int v=to[i];
if(dis[v]<dis[u]+cst[i]){
dis[v]=dis[u]+cst[i];
f[v]=min(f[u],wei[i]),ps[v]=i;
if(!vis[v])vis[v]=1,q.push(v);
}
}
}return dis[Ed]!=dis[0];
}
int Sol_EK(){
int res=0;
while(SPFA_Canit()){
int now=Ed;
while(now!=St){
int id=ps[now];
wei[id]-=f[Ed],wei[id^1]+=f[Ed];
now=to[id^1];
}res+=dis[Ed]*f[Ed];
}return res;
}
int main(){
n=read(),k=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
int x=read();
Add_edge(Num(i,j,0),Num(i,j,1),1,x);
Add_edge(Num(i,j,0),Num(i,j,1),k-1,0);
if(i<n)Add_edge(Num(i,j,1),Num(i+1,j,0),k,0);
if(j<n)Add_edge(Num(i,j,1),Num(i,j+1,0),k,0);
}
St=1,Ed=2*n*n;
cout<<Sol_EK()<<"\n";
return 0;
}
P4014 分配问题
这道题用费用流做是非常简单的，只需要建个模。
首先有源点汇点，然后从源点向每个人连一条容量为 \(1\)、费用为 \(0\) 的边。同样，从每一个工作向汇点连一条容量为 \(1\)、费用为 \(0\) 的边。
然后对于第 \(i\) 个人和第 \(j\) 个工作，连一条容量为 \(1\)、费用为 \(c_{i,j}\) 的边。
最后跑一个最大费用最大流和一个最小费用最大流就解决咯。
#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 2e5+5;
const LL INF = 0x3f3f3f3f3f3f3f3f;
LL n,St,Ed,a[55][55],dis[N],f[N],ps[N];
bool vis[N];queue<int> q;
LL tot=1,head[N],to[N],wei[N],cst[N],nxt[N];
LL read(){
LL su=0,pp=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
return su*pp;
}
void Add_edge(int x,int y,LL z,LL w){
to[++tot]=y,wei[tot]=z,cst[tot]=w;
nxt[tot]=head[x],head[x]=tot;
to[++tot]=x,wei[tot]=0,cst[tot]=-w;
nxt[tot]=head[y],head[y]=tot;return;
}
bool SPFA_small(){
while(!q.empty())q.pop();
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(St),dis[St]=0,vis[St]=1,f[St]=INF;
while(!q.empty()){
int u=q.front();vis[u]=0;q.pop();
for(int i=head[u];i;i=nxt[i]){
if(!wei[i])continue;int v=to[i];
if(dis[v]>dis[u]+cst[i]){
dis[v]=dis[u]+cst[i];
f[v]=min(f[u],wei[i]),ps[v]=i;
if(!vis[v])vis[v]=1,q.push(v);
}
}
}return dis[Ed]!=dis[0];
}
bool SPFA_big(){
while(!q.empty())q.pop();
memset(dis,-0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(St),dis[St]=0,vis[St]=1,f[St]=INF;
while(!q.empty()){
int u=q.front();vis[u]=0;q.pop();
for(int i=head[u];i;i=nxt[i]){
if(!wei[i])continue;int v=to[i];
if(dis[v]<dis[u]+cst[i]){
dis[v]=dis[u]+cst[i];
f[v]=min(f[u],wei[i]),ps[v]=i;
if(!vis[v])vis[v]=1,q.push(v);
}
}
}return dis[Ed]!=dis[0];
}
LL EK_small(){
LL res=0;
while(SPFA_small()){
int now=Ed;
while(now!=St){
int id=ps[now];
wei[id]-=f[Ed],wei[id^1]+=f[Ed];
now=to[id^1];
}res+=dis[Ed]*f[Ed];
}return res;
}
LL EK_big(){
LL res=0;
while(SPFA_big()){
int now=Ed;
while(now!=St){
int id=ps[now];
wei[id]-=f[Ed],wei[id^1]+=f[Ed];
now=to[id^1];
}res+=dis[Ed]*f[Ed];
}return res;
}
int main(){
n=read(),St=2*n+1,Ed=St+1;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
a[i][j]=read(),Add_edge(i,j+n,1,a[i][j]);
for(int i=1;i<=n;i++)Add_edge(St,i,1,0);
for(int i=1;i<=n;i++)Add_edge(i+n,Ed,1,0);
cout<<EK_small()<<"\n";
for(int i=1;i<=tot;i++)
to[i]=0,wei[i]=0,cst[i]=0,nxt[i]=0;
for(int i=1;i<=Ed;i++)head[i]=0;tot=1;
for(int i=1;i<=Ed;i++)
vis[i]=0,dis[i]=0,f[i]=0,ps[i]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)Add_edge(i,j+n,1,a[i][j]);
for(int i=1;i<=n;i++)Add_edge(St,i,1,0);
for(int i=1;i<=n;i++)Add_edge(i+n,Ed,1,0);
cout<<EK_big()<<"\n";
return 0;
}
P1251 餐巾计划问题
题意不难，重点是图论建模。废话。
首先拆点，把每天拆成早上和晚上。每天早上会得到新餐巾，每天晚上会得到脏餐巾。这些餐巾就是图中的流量，而花费就是每条边的费用，也就是我们最后要最小化的东西。
接下来具体考虑每一种情况下的建图：
- 从源点向第 \(i\) 天晚上连一条流量为当日所用餐巾数量 \(r_i\)、费用为 \(0\) 的边，表示当日使用餐巾并获得了脏餐巾。
- 从第 \(i\) 天早上向汇点连一条流量为当日所用餐巾数量 \(r_i\)、费用为 \(0\) 的边，表示向汇点提供 \(x\) 条新餐巾。连这个边的作用是为了跑最大流确认当日流满。
- 从第 \(i\) 天晚上向第二天晚上连一条流量为 \(\infty\)、费用为 \(0\) 的边，表示每天晚上可以把脏餐巾留到第二天晚上。注意不是早上，因为早上要获得的是新餐巾。
- 从第 \(i\) 天晚上向第 \(i+m\) 天早上连一条流量为 \(\infty\)、费用为 \(f\) 的边，表示每天晚上可以以单价 \(f\) 元的价格把脏餐巾送到快洗部并在第 \(i+m\) 天早上收到新餐巾。注意连边时要判断是否满足 \(i+m \le N\)。
- 从第 \(i\) 天晚上向第 \(i+n\) 天早上连一条流量为 \(\infty\)、费用为 \(s\) 的边，表示每天晚上可以以单价 \(s\) 元的价格把脏餐巾送到慢洗部并在第 \(in\) 天早上收到新餐巾。同样注意连边时判断是否满足 \(i+n \le N\)。
- 从源点向每一天早上连一条流量为 \(\infty\)、费用为 \(p\) 的边，表示每天早上可以以单价 \(p\) 元的价格购买新餐巾。
这玩意儿怎么这么复杂啊！
建完图直接跑板子最大流最小费用就可以啦。
```plaintext
#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int M = 1e5+5;
const LL INF = 0x3f3f3f3f3f3f3f3f;
LL n,St,Ed,m,t1,m1,t2,m2;
LL dis[M],f[M],ps[M];queue<int> q;bool vis[M];
LL tot=1,head[M],to[M],wei[M],cst[M],nxt[M];
LL read(){
LL su=0,pp=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
return su*pp;
}
void Add_edge(int x,int y,LL z,LL w){
to[++tot]=y,wei[tot]=z,cst[tot]=w;
nxt[tot]=head[x],head[x]=tot;
to[++tot]=x,wei[tot]=0,cst[tot]=-w;
nxt[tot]=head[y],head[y]=tot;return;
}
bool SPFA_Canit(){
while(!q.empty())q.pop();
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(St),dis[St]=0,vis[St]=1,f[St]=INF;
while(!q.empty()){
int u=q.front();vis[u]=0;q.pop();
for(int i=head[u];i;i=nxt[i]){
if(!wei[i])continue;int v=to[i];
if(dis[v]>dis[u]+cst[i]){
dis[v]=dis[u]+cst[i];
f[v]=min(f[u],wei[i]),ps[v]=i;
if(!vis[v])vis[v]=1,q.push(v);
}
}
}return dis[Ed]!=dis[0];
}
LL Sol_EK(){
LL res=0;
while(SPFA_Canit()){
int now=Ed;
while(now!=St){
int id=ps[now];
wei[id]-=f[Ed],wei[id^1]+=f[Ed];
now=to[id^1];
}res+=dis[Ed]*f[Ed];
}return res;
}
int main(){
n=read(),St=2*n+1,Ed=St+1;
for(int i=1;i<=n;i++){
LL x=read();
Add_edge(St,i,x,0);
Add_edge(i+n,Ed,x,0);
}m=read(),t1=read(),m1=read();
t2=read(),m2=read();
for(int i=1;i<=n;i++){
Add_edge(St,i+n,INF,m);
if(i<n)Add_edge(i,i+1,INF,0);
if(i+t1<=n)Add_edge(i,i+n+t1,INF,m1);
if(i+t2<=n)Add_edge(i,i+n+t2,INF,m2);
}cout<<Sol_EK()<<"\n";
return 0;
}
浙公网安备 33010602011771号