最大流
code
queue<int> q;
int dep[N],cur[N];
int bfs(){
memset(dep,0,sizeof(dep));
q.push(st);
dep[st]=1;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(dep[y] || !edge[i]) continue;
dep[y]=dep[x]+1;
q.push(y);
}
}
if(dep[ed]) return 1;
else return 0;
}
int dfs(int x,int flow){
if(x==ed) return flow;
for(int i=cur[x];i;i=nex[i]){
cur[x]=i;
int y=ver[i];
if(dep[y]==dep[x]+1 && edge[i]){
int d=dfs(y,min(flow,edge[i]));
if(d>0){
edge[i]-=d;
edge[i^1]+=d;
return d;
}
}
}
return 0;
}
int Dinic(){
int ans=0;
while(bfs()){
for(int i=1;i<=ed;i++){
cur[i]=head[i];
}
while(int d=dfs(st,inf)){
ans+=d;
}
}
return ans;
}
最大流最小割定理
对于一个网络流图 \(G=(V,E)\) 的最小割等于其最大流。
问题模型：
有 \(n\) 个物品和两个集合 \(A,B\) ，如果一个物品没有放入 \(A\) 集合会花费 \(a_i\) ，没有放入 \(B\) 集合会花费 \(b_i\) ；还有若干个形如 \(u_i,v_i,w_i\) 限制条件，表示如果 \(u_i\) 和 \(v_i\) 同时不在一个集合会花费 \(w_i\) 。每个物品必须且只能属于一个集合，求最小的代价。
线性代数
先钦定 \(b\) 的贡献全算上，然后考虑减少的量，要使其最小，又发现 \(a_i\) 等于 \(0,1\) 有不同贡献，\(a_i\) 和 \(a_j\) 组合又有不同贡献，所以考虑最小割，会有一下关系：
\[a+b=c_x+c_y (x,y=1)
\]
\[c+d=b_{xy}+b_{xx}+b_{yy}+b_{yx} (x,y=0)
\]
\[a+d+v2=c_x+b_{xy}+b_{yy}+b_{yx} (x=1,y=0)
\]
\[b+c+v1=c_y+b_{xy}+b_{yx}+b_{xx} (x=0,y=1)
\]
用解方程的方法让 \(a=c_x , b=c_y , c=b_{xx}+b_{xy} , d=b_{yy}+b_{yx}\)，然后求出 \(v_1,v_2\)，给 \(c,d\)求个和发现 \(c=\sum_{i}b_{xi}\) \(d=\sum_{i}b_{yi}\)。
费用流
每回 \(spfa\) 找费用最小的流。
code
queue<int> q;
int gpre[N],gpath[N];
int dist[N];
int spfa(int s,int t){
memset(gpre,-1,sizeof(gpre));
memset(dist,0x7f,sizeof(dist));
q.push(s);
dist[s]=0;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(edge[i] && dist[y]>dist[x]+cost[i]){
dist[y]=dist[x]+cost[i];
gpre[y]=x;
gpath[y]=i;
q.push(y);
}
}
}
if(gpre[t]==-1) return 0;
else return 1;
}
pair<int,int> EKF(){
int flow=0;
int ct=0;
while(spfa(s,t)){
int mi=(1ll<<20);
for(int x=t;x!=s;x=gpre[x]){
mi=min(mi,edge[gpath[x]]);
}
flow+=mi;
for(int x=t;x!=s;x=gpre[x]){
ct+=cost[gpath[x]]*mi;
edge[gpath[x]]-=mi;
edge[gpath[x]^1]+=mi;
}
}
return make_pair(flow,ct);
}
上面是保证最大流的前提下最小费用，下面是保证最小费用前提下最大流（相当于可行流）（区别很小）
code
int gpre[N*2],gpath[N*2],dist[N*2];
bool flat[N*2];
queue<int> q;
int spfa(int s,int t){
memset(gpre,-1,sizeof(gpre));
memset(dist,0x7f,sizeof(dist));
q.push(s);
dist[s]=0;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(edge[i] && dist[y]>dist[x]+cost[i]){
dist[y]=dist[x]+cost[i];
gpre[y]=x;
gpath[y]=i;
q.push(y);
}
}
}
if(gpre[t]==-1) return 0;
else return 1;
}
int n,m,k;
int cnt=(1ll<<60);
int EKF(){
int ct=0;
while(m--&&spfa(st,ed)){//---------------------------------------------<---------
int mi=1e9;
for(int x=ed;x!=st;x=gpre[x]){
mi=min(mi,edge[gpath[x]]);
}
int qwe=0;
for(int x=ed;x!=st;x=gpre[x]){
qwe+=cost[gpath[x]]*mi;
edge[gpath[x]]-=mi;
edge[gpath[x]^1]+=mi;
}
if(qwe>0) continue;
ct+=qwe;
}
return ct;
}
有上下界的网络流
无源汇有上下界可行流(也就是循环流)
可行流算法的核心是将一个不满足流量守恒的初始流调整成满足流量守恒的流。
我们一开始钦定每条边的流量为其下界，可以注意到的是此时每个点的入流量不等于出流量，将这个流量定义初始流。
所以我们进行调整，将原图的容量全部改为 \(up-down\)，这样如何调整总流量都在范围内，定义数组 \(A_i\) 等于 \(i\) 的入流量减去出流量。为了满足流量守恒，我们考虑在残量网络上求出一个另不满足流量守恒的附加流，使得这个附加流和我们的初始流合并之后满足流量守恒。
定义源点 \(st\)，汇点 \(ed\)。如果一个点 \(A_i>0\) 相当于要求附加流出流量大于入流量，为了让多出的出流量有一个来路，所以 \(st \rightarrow i\)，容量为 \(|A_i|\)；如果一个点 \(A_i<0\) 相当于要求附加流入流量大于出流量，为了让多出的入流量有一个出路，所以 \(i \rightarrow ed\)，容量为 \(|A_i|\)。
可以发现 \(A_i\) 之和为 \(0\)，因为每条边对两边的贡献互为相反数，设正 \(sum=\sum A_i (A_i>0)\)。
我们对 \(st-ed\) 跑最大流，如果最大流等于 \(sum\)，也就是可以跑满，说明有可行流的，反之没有。最后每条边可行流的流量 \(=\) 容量下界 \(+\) 附加流流量（跑完后反向边权值）
有源汇有上下界可行流
建出图 \(sst-eed\) 之后连一条 \(eed \rightarrow sst\) 下界为 \(0\)，上界为正无穷的边，转化为无源汇有上下界可行流，最后跑出来的可行流大小其实为 \(eed \rightarrow sst\) 反向边的大小。
有源汇有上下界最大流
我们跑完的可行流不一定是最大的，所以我们再在 \(sst-eed\) 之间的残余网络中跑最大流，最后 答案 \(=\) 可行流 \(+\) 之后跑的最大流。
注意这里判断是否可行是看 \(st-ed\) 最大流是否等于 \(sum\)。可行流的大小等于 \(eed \righttarrow sst\) 反向边的大小，别混淆。
例题Zoj3229 Shoot the Bullet
code
#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
const int inf=0x7f7f7f7f;
int st,ed;
int head[maxn],ver[maxn*maxn],nex[maxn*maxn],edge[maxn*maxn],tot=1;
void add(int x,int y,int v){
ver[++tot]=y,nex[tot]=head[x],head[x]=tot,edge[tot]=v;
ver[++tot]=x,nex[tot]=head[y],head[y]=tot,edge[tot]=0;
}
int A[maxn];
queue<int> q;
int dep[maxn],cur[maxn];
int bfs(){
memset(dep,0,sizeof(int)*(ed+1));
dep[st]=1;
q.push(st);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(edge[i]<=0 || dep[y]) continue;
dep[y]=dep[x]+1;
q.push(y);
}
}
if(dep[ed]) return 1;
else return 0;
}
int dfs(int x,int flow){
if(x==ed) return flow;
for(int i=cur[x];i;i=nex[i]){
cur[x]=i;
int y=ver[i];
if(dep[y]==dep[x]+1 && edge[i]>0){
int d=dfs(y,min(flow,edge[i]));
if(d>0){
edge[i]-=d;
edge[i^1]+=d;
return d;
}
}
}
return 0;
}
int Dinic(){
int ans=0;
while(bfs()){
for(int i=1;i<=ed;i++){
cur[i]=head[i];
}
while(int d=dfs(st,inf)){
ans+=d;
}
}
return ans;
}
signed main(){
// freopen("P5192_1.in","r",stdin);
// freopen("in.in","r",stdin);
int n,m;
while(scanf("%d%d",&n,&m)==2){
memset(A,0,sizeof(A));
tot=1;
memset(head,0,sizeof(head));
int sst=n+m+1,eed=sst+1;
st=eed+1,ed=st+1;
for(int i=1;i<=m;i++){
int g;
scanf("%d",&g);
add(n+i,eed,inf-g);
A[eed]+=g;
A[n+i]-=g;
}
int sum=0;
for(int i=1;i<=n;i++){
int c,d;
scanf("%d%d",&c,&d);
add(sst,i,d);
for(int j=1;j<=c;j++){
int t,l,r;
scanf("%d%d%d",&t,&l,&r);
t++;
add(i,n+t,r-l);
A[i]-=l;
A[n+t]+=l;
}
}
add(eed,sst,inf);
int pos=tot;
for(int i=1;i<=eed;i++){
if(A[i]==0) continue;
if(A[i]<0) add(i,ed,-A[i]);
else add(st,i,A[i]);
if(A[i]>0) sum+=A[i];
}
if(Dinic()!=sum){
printf("-1\n\n");
}
else{
int ans=edge[pos];
for(int i=head[st];i;i=nex[i]){
edge[i]=edge[i^1]=0;
}
for(int i=head[ed];i;i=nex[i]){
edge[i]=edge[i^1]=0;
}
for(int i=head[sst];i;i=nex[i]){
if(ver[i]==eed){
edge[i]=edge[i^1]=0;
}
}
st=sst,ed=eed;
ans+=Dinic();
printf("%d\n\n",ans);
}
}
}
有源汇上下界最小流
考虑反边的含义，反边每增加一，相当于正边减小一，所以我们给 \(sst-eed\) 反边跑最大流，那么 答案 \(=\) 可行流 \(-\) 反边最大流。
例题清理雪道
code
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000;
const int inf=(1<<20);
int st,ed;
int head[maxn*2],nex[maxn*maxn],ver[maxn*maxn],edge[maxn*maxn],tot=1;
void add(int x,int y,int v){
ver[++tot]=y,nex[tot]=head[x],head[x]=tot,edge[tot]=v;
ver[++tot]=x,nex[tot]=head[y],head[y]=tot,edge[tot]=0;
}
int A[maxn*maxn];
queue<int> q;
int dep[maxn],cur[maxn];
int bfs(){
memset(dep,0,sizeof(int)*(max(st,ed)+1));
dep[st]=1;
q.push(st);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
if(edge[i]<=0 || dep[y]) continue;
dep[y]=dep[x]+1;
q.push(y);
}
}
if(dep[ed]) return 1;
else return 0;
}
int dfs(int x,int flow){
if(x==ed) return flow;
for(int i=cur[x];i;i=nex[i]){
cur[x]=i;
int y=ver[i];
if(dep[y]==dep[x]+1 && edge[i]>0){
int d=dfs(y,min(flow,edge[i]));
if(d>0){
edge[i]-=d;
edge[i^1]+=d;
return d;
}
}
}
return 0;
}
int Dinic(){
int ans=0;
while(bfs()){
int mx=max(ed,st);
for(int i=1;i<=mx;++i){
cur[i]=head[i];
}
while(int d=dfs(st,inf)){
ans+=d;
}
}
return ans;
}
signed main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int m;
scanf("%d",&m);
for(int j=1;j<=m;j++){
int x;
scanf("%d",&x);
add(i,x,inf-1);
A[i]--,A[x]++;
}
}
int sst=n*2+1,eed=sst+1;
st=eed+1,ed=st+1;
for(int i=1;i<=n;i++){
add(sst,i,inf);
add(i,eed,inf);
}
add(eed,sst,inf);
int pos=tot;
int sum=0;
for(int i=1;i<=eed;i++){
if(A[i]==0) continue;
if(A[i]<0) add(i,ed,-A[i]);
else add(st,i,A[i]);
if(A[i]>0) sum+=A[i];
}
Dinic();
int ans=edge[pos];
for(int i=head[st];i;i=nex[i]){
edge[i]=edge[i^1]=0;
}
for(int i=head[ed];i;i=nex[i]){
edge[i]=edge[i^1]=0;
}
for(int i=head[sst];i;i=nex[i]){
if(ver[i]==eed){
edge[i]=edge[i^1]=0;
}
}
st=eed,ed=sst;
ans-=Dinic();
printf("%d",ans);
}