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;
}

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;
}

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; 
}