【学习笔记】网络流
背景
马上ICPC了，很惊奇的发现自己没整理网络流的板子。
最大流 dinic
这里选用的是二分图最大匹配的板子：飞行员配对方案问题
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18;
struct E
{
int to,next,lim;
E()
{
to=next=lim=0;
}
E(int x,int y,int z):to(x),next(y),lim(z)
{
}
};
vector<E> e;
vector<int> d,ls,cur;
int m,n;
void add(int u,int v,int lim)
{
e.push_back(E(v,ls[u],lim));
ls[u]=e.size()-1;
}
bool bfs(int S,int T)
{
d.assign(n+3,0);
d[S]=1;
queue<int> q;
q.push(S);
while(!q.empty())
{
int u=q.front(); q.pop();
for(int i=ls[u]; i; i=e[i].next)
{
int v=e[i].to;
if(d[v]>0||e[i].lim==0) continue;
d[v]=d[u]+1;
if(v==T) return 1;
q.push(v);
}
}
return 0;
}
int dfs(int u,int flow)
{
if(u==n+2||flow==0) return flow;
int res=0;
for(int &i=cur[u]; i; i=e[i].next)
{
int v=e[i].to;
if(d[u]+1!=d[v]||e[i].lim==0) continue;
int f=dfs(v,min(flow-res,e[i].lim));
e[i].lim-=f;
e[i^1].lim+=f;
res+=f;
if(flow==res) break;
}
return res;
}
int dinic(int S,int T)
{
int res=0;
while(bfs(S,T))
{
cur=ls;
int p=dfs(S,inf);
res+=p;
}
return res;
}
void O_o()
{
cin>>m>>n;
int S=n+1,T=n+2;
// vector E(n+3,vector<array<int,2>>());
e.push_back(E());
e.push_back(E());
ls.assign(n+3,0);
while(1)
{
int x,y;
cin>>x>>y;
if(x>y) swap(x,y);
if(x==-1&&y==-1) break;
add(x,y,1);
add(y,x,0);
}
for(int i=1; i<=m; i++)
{
add(S,i,1);
add(i,S,0);
}
for(int i=m+1; i<=n; i++)
{
add(i,T,1);
add(T,i,0);
}
cout<<dinic(S,T)<<"\n";
for(int u=m+1; u<=n; u++)
{
for(int i=ls[u]; i; i=e[i].next)
{
int v=e[i].to;
if(v<=n&&e[i].lim>0)
{
cout<<v<<" "<<u<<"\n";
}
}
}
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cout<<fixed<<setprecision(12);
int T=1;
// cin>>T;
while(T--)
{
O_o();
}
}
费用流
选用的题目：[NOI2008] 志愿者招募
建边规则：
u
−
>
v
:
f
=
f
l
o
w
,
w
=
c
o
s
t
u->v: f=flow, w=cost
u−>v:f=flow,w=cost
v
−
>
u
:
f
=
0
,
w
=
−
c
o
s
t
v->u: f=0, w=-cost
v−>u:f=0,w=−cost
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18;
struct E
{
int to,next,lim,cost;
E()
{
to=next=lim=cost=0;
}
E(int a,int b,int c,int d):to(a),next(b),lim(c),cost(d)
{
}
};
vector<E> e(2);
vector<int> ls,dis;
vector<bool> vis;
void add(int u,int v,int c,int w)
{
e.push_back(E(v,ls[u],c,w)); ls[u]=e.size()-1;
e.push_back(E(u,ls[v],0,-w)); ls[v]=e.size()-1;
}
int n,m,S,T,ans=0;
bool spfa()
{
vis.assign(n+4,0);
dis.assign(n+4,inf);
queue<int> q;
q.push(S);
vis[S]=1;
dis[S]=0;
while(!q.empty())
{
int u=q.front(); q.pop();
vis[u]=0;
for(int i=ls[u]; i; i=e[i].next)
{
int v=e[i].to;
if(e[i].lim==0||dis[v]<=e[i].cost+dis[u]) continue;
dis[v]=e[i].cost+dis[u];
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
return dis[T]<inf/2;
}
int dfs(int u,int flow)
{
vis[u]=1;
if(u==T)
{
return flow;
}
int res=0;
for(int i=ls[u]; i; i=e[i].next)
{
int v=e[i].to;
if(dis[v]!=dis[u]+e[i].cost||e[i].lim==0||vis[v]) continue;
auto p=dfs(v,min(flow,e[i].lim));
if(p)
{
e[i].lim-=p;
e[i^1].lim+=p;
res+=p;
ans+=p*e[i].cost;
flow-=p;
if(!flow) return res;
}
}
return res;
}
int costflow()
{
int res=0;
while(spfa())
{
vis[T]=1;
while(vis[T])
{
vis.assign(n+4,0);
res+=dfs(S,inf);
}
}
return res;
}
void O_o()
{
cin>>n>>m;
S=n+2; T=n+3;
ls.assign(n+4,0);
for(int i=1; i<=n; i++)
{
int x;
cin>>x;
add(i,i+1,inf-x,0);
}
add(S,1,inf,0);
add(n+1,T,inf,0);
for(int i=1; i<=m; i++)
{
int l,r,v;
cin>>l>>r>>v;
r++;
add(l,r,inf,v);
}
costflow();
cout<<ans<<"\n";
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cout<<fixed<<setprecision(12);
int T=1;
// cin>>T;
while(T--)
{
O_o();
}
}
无源汇可行流
本部分参考：https://zhuanlan.zhihu.com/p/324507636
定义：
下界网络：边流量为
l
l
l 组成的网络。
差网络：边流量为
r
−
l
r-l
r−l 组成的网络。
建图过程
- 把差网络的边加入图中，称为非附加边
- 建立超级源 S S SS SS，超级汇 T T TT TT
- 记 d u d_u du 为下界网络中流入的流量 - 流出的流量。
- 如果 d u > 0 d_u > 0 du>0，那么我们从 S S SS SS 向 u u u 连一条流量为 d u d_u du 的边，称为附加边。这样在最终的网络中，去掉附加边后，流出的流量会比流入的多 d u d_u du，平衡了下界网络。
- 同理，如果 d u < 0 d_u < 0 du<0，那么我们从 u u u 向 T T TT TT 连一条流量为 − d u -d_u −du 的边，称为附加边。
- 所有的附加边费用都应该为0
如果跑一遍最大流，附加边的流量没跑满，那么这张图就不存在可行流。
把所有边的流量加上
l
l
l 就是一个可行流。
有源汇可行流
在无源汇图的基础上，从 T T T 向 S S S 连一条流量上限为 i n f inf inf，费用为 0 0 0 的附加边。注意这是原图的源点和汇点，不是附加的。这样就把问题转换为了无源汇的可行流问题（因为流量平衡了）。可行流的大小等于新加的这条边的流量大小。
有源汇上下界最大流
把图中所有的附加边删掉，根据残余网络从
S
S
S 到
T
T
T 跑一遍最大流。这相当于把流量给榨干。再加上可行流就是最大流。
但其实除了 T T T 到 S S S 的那条附加边，其他的边是不用删的，因为他们已经流满了，并且 S S SS SS 和 T T TT TT 的 入度/出度为0，不会对答案产生影响。
有源汇上下界最小流
和最大流类似，从 T T T 到 S S S 跑一遍最大流，用可行流减去最大流即可。这相当于是把不必要的流量还回去。