lp3980 NOI2008 志愿者招募

一开始YY了一种连边方式,就是源点向第一个点连边,第一个点向最后一个点连边,每个边的流量是1,希望能通过一些奇奇怪怪的约束条件来保证能从1跑到n。
但是很快这个想法就被枪毙了——每一天需要消耗的人力是不同的。
怎么办呢?
我们可以考虑一种(我瞎取名叫)替换法的建模方法。
具体来说就是,先确定一个最大流,然后将其中的一些流量替换为必须要通过实际需要的路径才能跑过,这样就保证了答案的合法性。

#include<iostream>
#include<cstdio>
#include<queue>

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}
inline int Max(int A,int B){
	return A>B?A:B;
}

struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[400005];
int h[20005],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);
	Eadd(V,U,0,-C);
}
int n,m,s,t,vis[20005],dis[20005],val[20005],nw[20005],fa[20005];
std::queue<int> q;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	dis[s]=0,vis[s]=1,fa[t]=-1;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(e[i].w,val[p]);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;
}

long long ans=0,ans2=0;
inline void EK(){
	int p;
	while(SPFA()){
		p=t;
		ans2+=val[t];
		ans+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
}
int a[20005],tot=0;
//tot不能想当然地取最大值,而应该取和。
//这是因为,过程中可能存在一些情况,使得先雇佣某个志愿者会更优。 
void init(){
	scanf("%d%d",&n,&m);
	s=n+2,t=n+3;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		tot+=a[i];
	}
	++tot;
	add(s,1,tot,0),add(n+1,t,tot,0);
	for(int i=1;i<=n;++i){
		add(i,i+1,tot-a[i],0);
	}
	int l,r,c;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&l,&r,&c);
		add(l,r+1,tot,c);
	}
	EK();
	printf("%lld\n",ans);
}

int main(){
	init();
	return 0;
}

lp2050 NOI2012 美食节

这一题是SCOI2007修车的威力加强版。
用常规的写法显然是无法通过的。
我们考虑动态加边。
这样就可以最小化每一次松弛带来的影响,于是复杂度就变成了O(能过)
(才怪呢。我卡常卡了半天结果还是开了O2才过。)
(赶紧学zkw费用流)

#include<iostream>
#include<cstdio>
#include<queue>
#define calc(I,J) ((J-1)*sm+I)
#define calc2(I) (I+sm*m)

namespace IO{
	const int S = 1E6;
	char buf[S];
	int len=0,pos=0;
	inline char frc(){
		if(len==pos){pos=0,len=fread(buf,1,S,stdin);}
		if(len==pos){exit(0);}else{putchar(buf[pos]);return buf[pos++];};
	}
	inline int fri(){
		int fr=1,ch=frc(),x=0;
		while(ch<=32)ch=frc();
		if(ch=='-')fr=-1,ch=frc();
		while('0'<=ch&&ch<='9')x=x*10+ch-'0',ch=frc();
		putchar(ch);
		return x*fr;
	}
}

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[6600005];
int h[90005],et=-1;

inline void add(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
	e[++et]=(ee){U,0,-C,h[V]};
	h[V]=et;
}
//mp[i][j]表示第i种菜由第j名厨师做需要消耗的时间。 
int n,m,s,t,sm,vis[90005],dis[90005],val[90005],fa[90005],nw[90005],po[45],mp[45][105];
int q[90005];
int l,r;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	dis[s]=0,vis[s]=1,fa[t]=-1;
	l=1,r=0;
	q[++r]=s;
	register int p;
	while(l<=r){
		p=q[l++];
		vis[p]=0;
		for(register int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(val[p],e[i].w);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q[++r]=e[i].v;
				}
			}
		}
	}
	return fa[t]!=-1;
}
//倒数第I个,厨师J 
int ans;
inline void EK(){
	register int p,cnt,ck;
	while(SPFA()){
		cnt=fa[t]%sm,ck=fa[t]/sm+1;
		++cnt;
		//注意这里的逆hash 
		for(int i=1;i<=n;++i){
			add(calc2(i),calc(cnt,ck),1,cnt*mp[i][ck]);
		}
		p=t;
		ans+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
}
void init(){
	puts("2333");
	n=IO::fri(),m=IO::fri();
	for(int i=1;i<=n;++i){
		po[i]=IO::fri();
		sm+=po[i];
	}
	s=sm*m+n+1,t=sm*m+n+2;
	for(register int i=1;i<=t;++i){
		h[i]=-1;
	}
	for(register int i=1;i<=n;++i){
		for(register int j=1;j<=m;++j){
			mp[i][j]=IO::fri();
			add(calc2(i),calc(1,j),1,mp[i][j]);
		}
	}
	for(int i=1;i<=n;++i){
		add(s,calc2(i),po[i],0);
	}
	for(register int i=1;i<=sm*m;++i){
		add(i,t,1,0);
	}
	EK();
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}

lp2604 ZJOI2010 网络扩容

第一问没什么好说的。直接看第二问。
一个很直接的想法就是,在每条边上都加上一条容量为\(k\),费用为\(c_{e}\)的边。
但是仔细一想会发现一个问题:如果s到t有多条路径的话,上述的方法就会使得流量总额过大。
有什么好方法呢?
第一个直接的想法是发现源汇之间如果有多条路径的话,那么必然是将所有的流量k全都贪心地放在花费最小的那条路径上是最优的。
但是这显然是不可能的,考虑一个残余网络非空的情况。
故而我们换一种思路:在原来所有边上额外连流量为k的边的同时,再从n向一个虚拟汇点t连一条边。这样既可完成。

#include<iostream>
#include<cstdio>
#include<queue>

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}
struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[20005];
int h[20005],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);
	Eadd(V,U,0,-C);
}
int n,m,s,t,K,dis[20005],nw[20005],val[20005],fa[20005],vis[20005];
int u[20005],v[20005],w[20005],c[20005];
std::queue<int> q;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		dis[i]=INF;
		val[i]=INF;
		vis[i]=0;
	}
	q.push(s);
	dis[s]=0,vis[s]=1,fa[t]=-1;
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dis[e[i].v]>dis[p]+e[i].c&&e[i].w>0){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(e[i].w,val[p]);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;;
}

int answ=0,ansc=0;
inline void EK(){
	int p;
	while(SPFA()){
		p=t;
		answ+=val[t];
		ansc+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	} 
}


void init(){
	scanf("%d%d%d",&n,&m,&K);
	s=1,t=n;
	for(int i=1;i<=n+1;++i){
		h[i]=-1;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",u+i,v+i,w+i,c+i);
		add(u[i],v[i],w[i],0);
	}
	EK();
	printf("%d ",answ);
	for(int i=1;i<=m;++i){
		add(u[i],v[i],INF,c[i]);
	}
	add(t,t+1,K,0);
	++t;
	EK();
	printf("%d\n",ansc);
}

int main(){
	init();
	return 0;
}

lp3159 CQOI2012 交换棋子

首先是一个常见套路:将棋子的交换等价为棋子的移动——这很重要。我们不妨把交换看做黑子的移动。
那么我们考虑这个问题的弱化版:假设每个格子的移动次数没有限制,该怎么做。
很显然将每个格子拆成两个点,然后每个右点向相邻的左点连边,跑最大流即可。
对于一个黑子的移动,我们发现,如果一个格子是这个黑子中途经过的点,那么这个格子必然会消耗两次交换次数。
故而,我们给从左点到右点的边设置一个容量上限,其值为交换次数上限的一半。
但是这么做的话我们发现了一个问题:倘若一个点起始状态和结束状态不一样,这个模型是无法有效描述结果的。
这是因为,如果一个点的起始状态和结束状态不一样,那么它通过的次数必然是奇数。
我们考虑这样拆点:将每个点拆成左,中,右三个点。然后,将每个点的右点向它的所有相邻点的左点连边,流量1,费用0。表示某个棋子走向了它的另一个相邻的棋子。
从中点向右点连一条边,表示这个点移出去的次数。显然,如果最终情况是白的而初始情况是黑的,这个点应该会多移出去一次。
从左点向中点连一条边,表示这个点移进来的次数。显然,如果最终情况是黑的而初始情况是白的,这个点应该会多移进来一次。
我们考虑这个「多移进来」和「多移出去」对这个点可以参与的交换次数的影响。
假若限定次数是偶数,那么多出来的这一次移动将使得这个点能参与的交换次数少一次;倘若限定次数是奇数,那么多出来的这一次移动将不影响这个点能参与的交换次数。
所以,我们可以用形如\(\lfloor \frac{limit+[end>begin]}{2} \rfloor \)和\(\lfloor \frac{limit+[begin>end]}{2} \rfloor \)的式子来描述这两条边的流量。
然后,对于题目要求的最小交换次数,我们考虑将原来就存在的连边加上费用。这样就满足了题目的要求。

#include<iostream>
#include<cstdio>
#include<queue>

const int dx[8]={-1,-1,-1,0,0,1,1,1};
const int dy[8]={1,0,-1,1,-1,1,0,-1};

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[200005];
int h[1205],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);
	Eadd(V,U,0,-C);
}

int n,m,s,t,vis[1205],dis[1205],val[1205],fa[1205],nw[1205];

std::queue<int> q;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	vis[s]=1,dis[s]=0,fa[t]=-1;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(e[i].w,val[p]);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;
}
int answ=0,ansc=0;
inline void zkw(){
	int p;
	while(SPFA()){
		p=t;
		answ+=val[t];
		ansc+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
}

char begin[25][25],end[25][25],limit[25][25];
inline int calc(int X,int Y,int T){
	return T*n*m+(X-1)*m+Y;
}

void init(){
	scanf("%d%d",&n,&m);
	s=3*n*m+1,t=3*n*m+2;
	int cnt=0;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	for(int i=1;i<=n;++i){
		std::cin>>begin[i]+1;
	}
	for(int i=1;i<=n;++i){
		std::cin>>end[i]+1;
	}
	for(int i=1;i<=n;++i){
		std::cin>>limit[i]+1;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(begin[i][j]=='1'){
				++cnt;
				add(s,calc(i,j,1),1,0);
			}
			add(calc(i,j,1),calc(i,j,2),(limit[i][j]-'0'+(int)(begin[i][j]>end[i][j]))>>1,1);
			if(end[i][j]=='1'){
				add(calc(i,j,1),t,1,0);
			}
			add(calc(i,j,0),calc(i,j,1),(limit[i][j]-'0'+(int)(end[i][j]>begin[i][j]))>>1,1);
			for(int k=0;k<8;++k){
				int x=i+dx[k],y=j+dy[k];
				if(x>=1&&x<=n&&y>=1&&y<=m){
					//n,m!!!
					add(calc(i,j,2),calc(x,y,0),INF,0);
				}
			}
		}
	}
	zkw();
	printf("%d\n",(answ==cnt?ansc:-1)>>1);
}

int main(){
	init();
	return 0;
}

lp2153 SDOI2009 晨跑

题意简述:求一张图上不共点两点间最大路径数。
首先考虑不共边最大路径数,很容易可以想到大力上一个最大流,边流量为一。
然后考虑不共点最大路径数。我们发现,可以通过拆点来构成约束条件。具体来说就是将每个点拆成入点和出点,然后跑一个网络流。
现在还要求一个最短总路径长度,很容易可以想到费用流。具体来说,就将每一条边的费用设置为它的长度。然后跑一遍即可。

#include<iostream>
#include<cstdio>
#include<queue>

const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[100005];
int h[405],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);
	Eadd(V,U,0,-C);
}

int n,m,s,t,dis[405],val[405],fa[405],nw[405];
bool vis[405];
std::queue<int> q;
inline int spfa(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	vis[s]=1,dis[s]=0,fa[t]=-1;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(val[p],e[i].w);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;
}

void init(){
	scanf("%d%d",&n,&m);
	s=1,t=2*n;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int u,v,c;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&u,&v,&c);
		add(n+u,v,1,c);
	}
	for(int i=2;i<n;++i){
		add(i,n+i,1,0);
	}
	add(1,n+1,1926,0);
	add(n,2*n,1926,0);
	int ansW=0,ansC=0,p;
	while(spfa()){
		p=t;
		ansW+=val[t];
		ansC+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
	printf("%d %d\n",ansW,ansC);
}

int main(){
	init();
	return 0;
}

lp2805 NOI2009 植物大战僵尸

仔细阅读题意,我们发现,这道题本质上就是一个约束类问题:对于每一株植物,都存在一些植物,需要消灭掉它们才能消灭它。
故而,它就变成了一个这样的问题:存在一些植物,其中的一些要消灭了另外一些之后才能消灭,问收益最大化的方法。
如果我们对每一棵植物建点,然后从一棵植物向它的约束植物连边,那么问题就转化为:一张有向图,每个点都有点权,请选中其中的某些点,使得每个点的后继都在这张图中。
这是一类被称为「最大权闭合子图问题」的问题。这种问题的解决方案是,从源点向正权点连权值为点权的边;从负权点向汇点连权值为点权的绝对值的边。原图中的边流量无穷大。
那么,答案就是总权值减去最小割。


下面我们来证明这种建模方式的合法性和最优性。
我们令从源点连出的边被割掉表示不选中这个点,连向汇点的边被割掉表示选中这个点。
那么,最终的结果必然是一个闭合子图。
这是因为,对于这张图的最小割,当你选中一个节点之后,这个点的所有后继负权节点都一定被割掉/选中了(根据割的性质显然);
这个点的所有后继正权节点都一定不被割/选中了(根据最小割的性质,割掉这些边没有意义)。
并且,任何一个闭合子图的选法都至少可以对应一个割法。
这是因为,对于原图中的某一种连接方法,都可以通过割掉不在其之中的所有负权边和在其之中的所有负权边来使其对应。
同时,根据我们此前的定义,最小割的值意味着没选中的正权点的值与选中的负权点的值的绝对值的和。故而,答案便是正权店的值的和减去最小割的值。
而最小割是要尽量小的,故而最小割可以得到最优答案。


PS:
这一题应当考虑死锁情况,想象一个无限攻击力和攻速的豌豆射手。(不考虑连样例都过不了)(但是尽管这样还是能够拿到80分)
具体处理方法就大力上一个拓扑排序即可。把所有需要缩掉的点打个标记,然后令这些点在网络流中不存在。
然而,如果我们直接写一个拓扑排序的话,还是只能得到80分的好成绩——这是因为这张图需要对反图进行拓扑排序。
细想,因为这张图上每一条有向边的终点一旦被删去,那么它的所有前驱也都是不能存在的。
故而,对反图进行拓扑排序找环并删去才能符合题目的要求。


#include<iostream>
#include<cstdio>
#include<queue>

const int INF=2147483647;
const int VERYBIG=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

int n,m,s,t,nw[1005],dep[1005],val[1005];

struct ee{
	int v;
	int w;
	int nxt;
}e[1000005];
int h[1005],et=-1,in[1005];
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
	++in[U];
}

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		nw[i]=h[i];
		if(dep[i]>-2){		
			dep[i]=INF;
		}
	}
	q.push(s);
	dep[s]=0;
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;;
				q.push(e[i].v); 
			}
		}
	}
//	printf("%d\n",dep[t]);
	return dep[t]<INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				V-=val;
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				} 
			}
		}
	}
	return cnt;
}

inline int calc(int X,int Y){
	return X*m+Y+1;
}

inline int dinic(){
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	return ans;
}
inline int srt(){
	for(int i=1;i<=t;++i){
		if(!in[i]){
			q.push(i);
		}
		dep[i]=-2;
	}
	int RT=0,p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		dep[p]=0;
		if(val[p]>0){
			RT+=val[p];
		}
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(!e[i].w){
				if(!--in[e[i].v]){
					q.push(e[i].v);
				}
			}
		}
	}
	return RT;
}

void init(){
	scanf("%d%d",&n,&m);
	s=n*m+1,t=n*m+2,et=-1;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int x,y,z;
	for(int i=1;i<=n*m;++i){
		scanf("%d",&x);
		val[i]=x;
		x>0?(add(s,i,x),0):(x==0?0:(add(i,t,-x),0));
		scanf("%d",&x);
		for(int j=1;j<=x;++j){
			scanf("%d%d",&y,&z);
			add(calc(y,z),i,VERYBIG);
		}
		if(i%m){
			add(i,i+1,VERYBIG);
		}
	}
	int tot=srt();
	printf("%d\n",tot-dinic());
}

int main(){
	init();
	return 0;
}

lp2774 方格取数问题

这是一道最小割转最大流的例题。
首先,我们发现,这一题要求我们求的是所取和。然后容易知道,所取和等于总和减去舍弃和。
故而,我们要使得所取和最大,就只需要使得舍弃和最小。
尝试用所取和来建图并且跑最大流,发现,它并不是那么容易地建成一个可靠的图。
正难则反,我们考虑怎么样才能让舍弃和最小。
于是尝试用舍弃和最小来建图并且跑最小割。观察题目的性质我们发现,所有的坐标和的奇偶性相同的方格,永远是互不影响的。
这启发我们建一个二分图。
我们不妨将奇点建在左侧,偶点建在右侧。然后从源点向奇点连容量为数值的边;从偶点向汇点连容量为数值的边。
于是,很显然,当我们割掉任何一条边的时候,就意味着相应的点是不取的。
接着我们将相邻的黑白点连容量为无穷大的边,这意味着这两个点之间至少有一个不能取。
然后跑最大流得到最小割即可。

#include<iostream>
#include<cstdio>
#include<queue>


const int INF=2147483647;
const int VERYBIG=0x3f3f3f3f; 

inline int Min(int A,int B){
	return A<B?A:B;
}


struct ee{
	int v;
	int w;
	int nxt;
}e[200005];
int h[40005],et=-1;
int dep[40005],nw[40005];

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}

inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}

int n,m,s,t;

inline int calc(int X,int Y){
	return (X-1)*m+Y;
}

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				V-=val;
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				}
			}
			
		}
	}
	return cnt;
}

inline int dinic(){
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	return ans;
}

void init(){
	scanf("%d%d",&n,&m);
	s=n*m+1,t=n*m+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int x,cnt=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&x);
			cnt+=x;
			if((i+j)&1){
				add(s,calc(i,j),x);
				if(i+1<=n){
					add(calc(i,j),calc(i+1,j),VERYBIG);
				}
				if(i-1>=1){
					add(calc(i,j),calc(i-1,j),VERYBIG);
				}
				if(j+1<=m){
					add(calc(i,j),calc(i,j+1),VERYBIG);
				}
				if(j-1>=1){
					add(calc(i,j),calc(i,j-1),VERYBIG);	
				}
			}else{
				add(calc(i,j),t,x);
			} 
		}
	}
	printf("%d\n",cnt-dinic());
}

int main(){
	init();
	return 0;
}

lp3381 【模板】最小费用最大流

首先我们需要掌握网络流的相关知识。
然后,我们仔细观察费用流问题,我们发现,这一类问题的本质上就是让我们求一个带路径长度的最大流。
故而,我们考虑,对于相同的流量,尽可能地从费用小的一条路走过去——这是一种很显然的贪心。
具体的实现似乎也并不难,只需要将原来的朴素求法(EK)稍微更改一下,将反边的花费变成相反数,然后求最短路即可。
考虑到负权边的可能,用SPFA会比较快。当然如果只有正权边显然是可以Dijkstra的。

#include<iostream>
#include<cstdio>
#include<queue>

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
    return A<B?A:B;
}
struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[100005];
int h[5005],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);Eadd(V,U,0,-C);
}
int n,m,s,t,dis[5005],val[5005],fa[5005],nw[5005];
bool vis[5005];
std::queue<int> q;
inline int spfa(){
	for(int i=1;i<=n;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	while(!q.empty()){
		q.pop();
	}
	vis[s]=1,dis[s]=0,fa[t]=-1;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(val[p],e[i].w);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;
}
void init(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    int u,v,w,c;
    for(int i=1;i<=n;++i){
        h[i]=-1;
    }
    for(int i=1;i<=m;++i){
        scanf("%d%d%d%d",&u,&v,&w,&c);
        add(u,v,w,c);
    }
    int ansW=0,ansC=0,p;
    while(spfa()){
    	p=t;
    	ansW+=val[t];
    	ansC+=val[t]*dis[t];
    	while(p!=s){
    		e[nw[p]].w-=val[t];
    		e[nw[p]^1].w+=val[t];
    		p=fa[p];
		} 
    }
    printf("%d %d\n",ansW,ansC);
}

int main(){
    init();
    return 0; 
}

lp2766 网络流24题-最长不下降子序列问题

这是一道看起来很简单的麻题。
很显然可以发现第一问就是直接n^2DP求一个答案。
第二问模拟寻找最长不下降子序列的过程。
第三问改几条边再跑一遍。
但是要注意很多很多细节。
比如说,建模的时候应该反着建。
再比如说,对于最长长度只有1的情况应当格外注意,因为这可能会导致各种错误。
写起来还是有点烦心的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>

const int INF=0x3f3f3f3f;
const int BIG=19260817;
inline int Min(int A,int B){
	return A<B?A:B;
}

inline int Max(int A,int B){
	return A>B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[250005];
int h[2005],et=-1;

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et; 
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}

int dep[2005],nw[2005],a[505];
int n,s,t,len;
std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF,nw[i]=h[i];
	}
	dep[s]=1;
	while(!q.empty()){
		q.pop();
	}
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
//	for(int i=1;i<=t;++i){
//		printf("%d ",dep[i]);
//	}
//	puts("");
	return dep[t]^INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(V,e[i].w));
			if(val){
				cnt+=val;
				V-=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				}
			}
		}
	}
	return cnt;
}
int f[505];
inline void slv1(){
	for(int i=1;i<=n;++i){
		f[i]=1;
		for(int j=1;j<i;++j){
			if(a[i]>=a[j]){
				f[i]=Max(f[i],f[j]+1);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		ans=Max(ans,f[i]);
	}
	len=ans;
	printf("%d\n",ans);
}

inline int dinic(){
	int RT=0;
	while(bfs()){
		RT+=dfs(s,INF);
	}
	return RT;
}

inline void slv2(){
	s=2*n+1,t=2*n+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	et=-1;
	for(int i=1;i<=n;++i){
		if(f[i]==len){
			add(i+n,t,1);
		}
		if(f[i]==1){
			add(s,i,1);
		}
		add(i,i+n,1);
		for(int j=1;j<i;++j){
			if(a[i]>=a[j]&&f[j]+1==f[i]){
				add(j+n,i,1);
			}
		}
	}
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	printf("%d\n",ans);
	add(1,n+1,BIG),add(s,1,BIG);
	if(f[n]==len){
		add(n,2*n,BIG),add(2*n,t,BIG);
	}
	while(bfs()){
		ans+=dfs(s,INF);
	}
	printf("%d\n",ans);
}

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	slv1();
	slv2();
}
int main(){
	init();
	return 0;
}

lp2764 网络流24题-最小路径覆盖问题


(其实建图方法已经写在题目里了。)
(这一题是一道匈牙利的裸题,考场上二分图最大匹配仍然建议使用匈牙利(因为在实现复杂度上有巨大优势),我纯粹练一下当前弧优化Dinic。)
首先有一个定理。将一张有向图上的每一个点都拆点成入点和出点,连边后形成一张二分图,那么原图的最小路径覆盖,就是顶点数减去这张二分图的最大匹配。
考虑感性地证明这个定理。
每一次匹配,事实上就意味着,一条路径可以额外走过一个点。这样就减少了一个路径覆盖。
所以,当匹配次数最大的时候,路径覆盖数就最小了。
答案用并查集处理一下输出。


#include<iostream>
#include<cstdio>
#include<queue>
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[20005];
int h[2005],et=-1;
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}
int dep[2005],nw[2005],f[2005];
int n,m,s,t;

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
}
inline int dfs(int X,int V){
	if(V<=0||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i; 
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				cnt+=val;
				V-=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(V<=0){
					break;
				}
			}
		}
	}
	return cnt;
}

inline int fnd(int X){
	for(int i=h[X+n];i>=0;i=e[i].nxt){
		if(1<=e[i].v&&e[i].v<=n){
			if(e[i].w){
				return e[i].v;
			}
		}
	}
	return X;
}
inline int fa(int X){
	return f[X]^X?f[X]=fa(f[X]):X;
}
inline void prnt(int X){
	for(int i=h[X];i>=0;i=e[i].nxt){
		if((n+1)<=e[i].v&&e[i].v<=(n<<1)&&!e[i].w){
			printf("%d ",e[i].v-n
			);
			prnt(e[i].v-n);
			return;
		}
	}
}
bool vis[2005];
void init(){
	scanf("%d%d",&n,&m);
	s=(n<<1)+1,t=(n<<1)+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int u,v;
	for(int i=1;i<=n;++i){
		add(s,i,1);
		add(n+i,t,1);
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,n+v,1);
	}
	int ans=n;
	while(bfs()){
		ans-=dfs(s,INF);
	}
	for(int i=1;i<=n;++i){
		f[i]=i;
	}
	for(int i=1;i<=n;++i){
		f[i]=fnd(i);
	}
	for(int i=1;i<=n;++i){
		fa(i);
	}
	for(int i=1;i<=n;++i){
		if(f[i]==i){
			printf("%d ",i);
			prnt(i);
			puts("");
		}
	}
	printf("%d\n",ans); 
}

int main(){
	init();
	return 0;
}

lp2763 网络流24题-试题库问题

对于这一题,我们建三层的边来描述题目中的约束。
对于每道题建一个点,源点连一条容量为1的边到每一个点,表示每道题最多只能被选取一次。
对于每个种类建一个点,每一个点连一条容量为1的边到它所属的所有类,表示它仅可以被作为这个类来选取。
每个种类连一条容量为这个种类需要的选取次数的边到汇点,表示这个种类最多需要被选取的次数。
然后,跑一遍当前弧优化Dinic最大流,如果需要选取的总题数都能选取到,流量就等于需要选取的总题数。
当然也可以大力拆点跑二分图匹配,不过那样似乎更难写的样子。

#include<iostream>
#include<cstdio>
#include<queue>
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[40005];
int h[2005],et=-1;
int dep[2005],nw[2005];

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}

inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0); 
}

int n,m,s,t,Sans=0,tot; 

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
} 
//V表示从源点到当前路径上的剩余流量,cnt表示这个点向后流了多少流量。 
inline int dfs(int X,int V){
	if(V<=0||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(V,e[i].w));
			if(val){
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				V-=val;
				if(V<=0){
					break;
				}
			}
		}
	}
	return cnt;
}

void init(){
	scanf("%d%d",&m,&n);
	s=m+n+1,t=m+n+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
//	注意初始化。 
	int p,x;
	for(int i=1;i<=m;++i){
		scanf("%d",&x);
		Sans+=x;
		add(n+i,t,x);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&p);
		add(s,i,1);
		for(int j=1;j<=p;++j){
			scanf("%d",&x);
			add(i,n+x,1);
//			注意哈希。 
		}
	}
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
		printf("%d\n",ans); 
	}
	if(ans<Sans){
		puts("No solution!");
		return;
	}
	for(int i=1;i<=m;++i){
		printf("%d: ",i);
		for(int j=h[n+i];j;j=e[j].nxt){
			if((j&1)&&(e[j].w==1)&&(e[j].v!=t)){
				printf("%d ",e[j].v);
			}
		}
		puts("");
	}
}

int main(){
	init();
	return 0;
}

lp5030 长脖子鹿放置

观察这一题的攻击方式,我们可以发现一个特点——所有奇数行的长颈鹿都攻击不到偶数行的长颈鹿,反之亦然。
所以,我们对奇偶的长颈鹿分开考虑,这显然是一张二分图。
于是类同于骑士共存问题,我们建一个二分图,跑匈牙利。
对于\(200\)的数据范围,匈牙利的小常数是可以卡过去的。
但是T了两个点,获得了80分的好成绩。
然后我们考虑一个对于vis数组的常数优化。
对于vis数组,我们定义一个变量dep,表示当前是第dep次匹配。这样就不必每次都清空vis数组了。
第二个就是,由于连的边是确定的,故而我们可以在线计算目的边,这样可以减少很多寻址时间。
另外就是对图的遍历顺序的优化。用了出题人的松松松顺序之后最终通过此题。

#include<iostream>
#include<cstdio>

const int dx[8]={3,3,-3,-3,1,1,-1,-1};
const int dy[8]={-1,1,-1,1,3,-3,3,-3};

bool mp[205][205];
int vis[40405],dep=0;
int n,m,q,usd[40405];
//注意数组大小。 

inline int calc(int X,int Y){
	return (X<=0||Y<=0||X>n||Y>m||mp[X][Y])?0:X*m+Y;
} 

inline bool dfs(int X){
	int v;
	for(int i=0;i<8;++i){
		v=calc((X-1)/m+dx[i],(X-1)%m+1+dy[i]);
//		注意还原信息。 
		if(v&&vis[v]!=dep){
			vis[v]=dep;
			if(!usd[v]||dfs(usd[v])){
				usd[v]=X;
				return 1;
			}
		}
	}
	return 0;
}

void init(){
//	mp[n][m]->mp[x][y] 
	scanf("%d%d%d",&n,&m,&q);
	int x,y;
	for(int i=1;i<=q;++i){
		scanf("%d%d",&x,&y);
		mp[x][y]=1;
	}
	int ans=n*m-q;
	for(int i=1;i<=n;i+=2){
		for(int j=1;j<=m;++j){
			if(mp[i][j]){
				continue;
			}
			++dep;
			ans-=dfs(calc(i,j));
		}
	}
//	for(int i=0;i<=n+1;++i){
//		for(int j=0;j<=m+1;++j){
//			printf("%2d ",calc(i,j));
//		}
//		puts("");
//	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}

lp3355 网络流24题-骑士共存问题

首先我们观察这道题。
暴力地状压DP或者之类的操作显然会MLE/TLE。
我们发现,横坐标和纵坐标相加的和的奇偶性相同的格子永远不可能互相攻击到。
故而我们考虑建一张二分图。将横纵坐标的和的奇偶性不同的格子分别放在左右边,然后在能相互攻击到的点之间连边。依据题意,不能相互攻击到,所以答案即是这张图的最大独立集。

二分图最大独立集应当如何求得?我们有一个定理:一张二分图的最大独立集的大小等同于顶点数它的最大匹配的数量。
我们考虑感性地证明这个定理。
很容易可以发现,两个点不能被同时选取,当且仅当它们之间有连边。
又因为,有连边的两个点必然是属于二分图的两端的。
故而,如果有两个点不能被同时选取,它们必然可以构成一个匹配。
对于二分图上的最大匹配,所有没有被匹配的点都可以被选取。这非常的显然,因为没有被匹配到的点之间必然没有连边。如果有连边,那么就可以增加匹配,与最大匹配矛盾。
而,对于每一个匹配,都可以选取一组匹配中的一个点。这是因为,对于一些连通的匹配,它们有且仅有一个部分(左边或者右边)会和未匹配点连接。
这也是很显然的,因为如果不是这样的话,就存在一条新的增广路径,就可以得到更多的匹配了。
注意:坐标如何哈希成一个数字。

#include<iostream>
#include<cstdio>

const int dx[8]={-2,-1,1,2,-2,-1,1,2};
const int dy[8]={1,2,2,1,-1,-2,-2,-1}; 

struct ee{
	int v;
	int nxt;
}e[160005];
int h[40005],et=0;

inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et; 
}

bool vis[40005],mp[205][205];
int n=0,m=0,usd[40005];

inline int calc(int X,int Y){
	return (X-1)*n+Y;
//	注意坐标哈希成数字的方式。 
}

inline bool dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		if(!vis[e[i].v]){
			vis[e[i].v]=1;
			if(!usd[e[i].v]||dfs(usd[e[i].v])){
				usd[e[i].v]=X;
				return 1;
			}
		}
	}
	return 0;
}
int st[40005],tp=0;
char out[205][205];
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			mp[i][j]=0;
			usd[calc(i,j)]=0;
			out[i][j]='O';
		}
	}
	int x,y;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&x,&y);
		mp[x][y]=1;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
//			printf("[%d %d] ",i,j);
			if(mp[i][j]||((i+j)&1)){
//				注意不是每次跳2而是判奇偶性。 
				continue;
			}
			st[++tp]=calc(i,j);
			out[i][j]='@'; 
			//注意有障碍的不仅是结束点,还有出发点。 
			for(int k=0;k<8;++k){
				x=i+dx[k],y=j+dy[k];
				if(x<=0||y<=0||x>n||y>n||mp[x][y]){
					continue;
				}
				out[x][y]='X';
				add(calc(i,j),calc(x,y));
			}
		}
	}
//	for(int i=1;i<=n;++i){
//		for(int j=1;j<=n;++j){
//			putchar(out[i][j]);
//		}
//		puts("");
//	}
	int ans=n*n-m;
//	减去被挖掉的点 
	for(int i=1;i<=tp;++i){
		for(int j=1;j<=n*n;++j){
			vis[j]=0;
		}
		ans-=dfs(st[i]);
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
} 

lp2756 网络流24题-飞行员配对方案问题

这是一个裸的配对问题。
我们可以建成一个二分图然后跑匈牙利。

#include<iostream>
#include<cstdio>
bool mp[105][105],vis[105];
int n,m,usd[105];

inline int dfs(int X){
    for(int i=1;i<=m;++i){
        if(!mp[X][i]){
            continue;
        }
        if(!vis[i]){
            vis[i]=1;
            if(!usd[i]||dfs(usd[i])){
                usd[i]=X;
                return 1;
            }
        }
    }
    return 0;
}

void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            mp[i][j]=mp[j][i]=0;
        }
    }
    int x=1,y=1;
    //你绝对想不到的错误——x,y没有初始化,导致判断它们的初始值的时候出现错误。 
    while(x>=0&&y>=0){
        scanf("%d%d",&x,&y);
        y-=n;
        mp[x][y]=1;
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            vis[j]=0;
        }
//        for(int j=1;j<=m;++j){
//        	printf("%d ",usd[j]);
//		}
//		puts("");
        ans+=(int)dfs(i);
    }
    printf("%d\n",ans);
    for(int i=1;i<=m;++i){
        if(usd[i]){
            printf("%d %d\n",usd[i],i+n);
            //注意这里要将编号还原。并且别输出反了。 
        }
    } 
}

int main(){
    init();
    return 0;
}

lp3376 【模板】网络最大流

全机房就我一个还不会网络流了。
下面我整理一下网络流的基本概念,辅助自己理解。


首先关于网络流的定义。形式化地说,网络流是一张图\(G(V,E)\)(有时也指这张图的一个状态),满足以下性质:
1.流量上限:对于任意一条边\(e\in E\),存在一个属性\(c_{e}\),定义它为这条边的流量上限。
2.流量受限:对于任意一条边\(e\in E\),存在一个属性\(0\le f_{e}\le c_{e}\),定义它为这条边当前的流量。
3.流量守恒:对于任意一个点\(v\),满足:\(\sum_{i\in{a|a_{v}=v,a\in E}}f_{i}=\sum_{j\in{b|b_{u}=v,b\in E}}f_{j}\)
4.源点汇点:存在两个点,分别叫做源点和汇点。其中,源点能够流出无穷多流量,而汇点能够流入无穷多流量。
若一个网络流的某一个状态满足上述所有性质,我们就称这个状态是合法的。
我们定义,对于一张网络流,使得它从源点流向汇点的流量最大的状态,为最大流。
求解最大流,就是指,求解最大流的状态。
为了辅助求解这个问题,我们可以考虑对于每一条边\(e\)都建一条反边\(e’\)。它的方向与原边相反。且\(f_{e’}=f_{e}\)
那么,所有的反边构成了另一张图\(G(E’,V)\),它描述的是它的原边已经走过的流量。
将一张图上的每一条边都只保留它的当前剩余流量\(f_{e}\),这张图可以被认为是对原图的流量空余的描述。故而我们称这张图为残余网络。

我们定义增广路径,指的是,在包括反边的残余网络的一条路径上面的一条路径,使得路径上的每一条原边都是不满的,且路径上每一条反边都是非空的。
对于关于这条路径上的所有原边,将其流量上限减去当前流量的值减去最小值,再对路径上每一条反边的当前流量值取最小值,再对两个最小值取最小值。
然后将所有原边的流量加上这个最小值,并将每一条反边的流量减去这个最小值(对应的反/原边同时减/加相应值)。 我们称这样一个操作为增广,称操作中减少反边流量的子操作为撤销。
如果当前图不是处于最大流的状态,那么一定可以找到一个增广路;如果当前图属于最大流的状态,那么一定没有增广路。
我们朴素地考虑如何利用增广来取得最大路径。如果我们每一次都暴力地寻找整个网络上的一条可行增广路并且增广(这似乎被称作F-F算法),在很糟糕的情况下,可能会出现很多次反复地增广而只增加很少的流量的情况。
在上诉的算法中,可能存在一种情况,就是,一条边被反复地增广-撤销多次。这样无形中增大了很多复杂度。
我们考虑上诉的情况是如何产生的。很显然,经过一次撤销操作之后,当前的路径的长度减少了一条边,而原来经过那条边的那些流量所在的路径上的长度也减少了一条边。
那么反复地增广-撤销操作的一个很大的原因,便是,第一次增广到这条边的时候的路径经过的边数太多。
如果每一次搜索增广路径的时候,都尽可能搜索边数尽可能少的一条边,那么便可以使得增广-撤销操作尽可能少。(这似乎被称作E-K算法)
上述的算法都可以被称作是朴素的算法。但复杂度最坏情况下可能会被卡到非常大,大概是\(O(n\times m^2)\)级。


下面是一个对于这个算法的正确性的感性证明。
我们首先证明,每一次增广之后,图上流过的流量都增多。
对于一次增广,当我们流过一条边的时候,流过的流量存在两种情况:
1.这些流量走过的是反边。
2.这些流量走过的是原边。
对于流过原边的流量,很显然无论如何可以流的,并且会将原图的状况改进得更优。
而对于流过反边的流量,可以视为将这些流量还原,然后原来流到这条边的那些流量,现在从当前路径流过这条边之后的那部分流走;而当前流到这条边的流量,则从之前流过这条边的那些流量的后半部分流走。
所以,每一次增广,总是会导向一个合法状态。
又因为,每一次增广之后,源点都会流出更多的流量,汇点都会收到更多的流量,所以整张图流过的流量增加了。

然后我们考虑证明,当不再能增广的时候,图上处于最大流的状态。
当走过一条边的时候,我们事实上完成了一次「反悔」,也就是指,让之前从这里走的一些流量往另一个方向走了。
如果,不再可以增广,这就意味着,无论反悔到什么程度、无论怎么改变之前已有的流量的路径,都无法找到一条新的路径使得流量可以通过。
即,哪怕是在反悔最多的情况下,也找不到一条能够产生更多流量的路径。
那么,我们就可以断言这个状态已经是最大流的状态了。


回到算法本身上。下面我们考虑优化这个朴素算法。\(O(n\times m^2)\)的复杂度显然是不可接受的。
Dinic算法就是一种对上述朴素算法的优化。
我们考虑一种被称为「多路增广」的操作。这种操作也是Dinic的核心。
对于每一次多路增广,我们首先将整张图dfs一遍,预处理出深度小于源汇距离的所有节点的深度。这样我们得到了一张分层图。
然后我们从源点开始进行一种特殊的DFS——每一次访问的节点的深度必须比前一个节点深,并且搜索经过的边必须是可以增广的边。
当我们搜索到汇点的时候,便开始沿着来路回溯,直到回溯到第一个「来路仍然可以继续增广」并且「连着其他还可以被继续增广的边」的节点为止,然后继续向下搜索。
如果回溯到了源点,多路增广结束。
然后,对剩下可以走的部分,重新计算深度,并重跑增广,直到不能再增广为止。
对于每一次多路增广,我们可以以\(O(nm)\)的复杂度遍历完成对某一个特定深度的所有增广操作。 而多路增广显然是最多只会被执行\(n\)次的。故而这么做的复杂度是\(O(n^2+m)\)的。
我们就得到了一个相对较优的算法。


#include<iostream>
#include<cstdio>
#include<queue>

const int INF = 0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[200005];
int h[10005],et=-1;
int n,m,s,t,ans=0,dep[10005],nw[10005];
inline void add(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=n;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
}

inline int dfs(int X,int V){
	if((V<=0)||(X==t)){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(V,e[i].w));
			if(val){
				cnt+=val;
				V-=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(V<=0){
					break;
				}
			}
		}
	}
	return cnt; 
}

void init(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	int u,v,w;
	for(int i=1;i<=n;++i){
		h[i]=-1;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,0);
	}
	while(bfs()){
		ans+=dfs(s,INF);
		//注意应当填写起始点。 
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0; 
}