题解：P1006 [NOIP 2008 提高组] 传纸条

可以费用流，但是疑惑的是题解区没有费用流。

我们发现，这要找两条路去传纸条，而每个人有个好心程度且只能传一次。

于是很容易设计费用流，对于每个点流量为

1

，费用为那个点的好心程度。

每个边流量为

1

，费用为

0

。

跑最大费用最大流，设

s

为起点，

t

为终点。

因为小渊传完后需要回传，所以

s=t

，但是这样

s=t

就直接死循环了。

并且在费用流中，点，是不能有流量和费用的。

那咋办，我们化点为边。

可以这样，把点拆成一个入点和一个出点。

入点指向出点的边流量和费用就是我们之前讨论的那个点的。

每个那个点的入点都指向它的入边，出边同样。

我们

s

设为小渊的出点，

t

为小渊的入点，也能避免死循环的问题。

跑最大费用最大流刚好满足题意。

代码。

CPP

//Dinic 算法  
#include<bits/stdc++.h>
using namespace std;
// #define int long long
int n,m,s,t;
int head[80010],to[240010],nxt[240010],val[240010],cost[240010],tot=1;
void add(int u,int v,int w,int c){
	to[++tot]=v,val[tot]=w,cost[tot]=c;
	nxt[tot]=head[u];
	head[u]=tot;
}
int maxflow,maxcost,dis[80010],now[80010],cnt[80010];
bool vis[80010];
bool spfa(){
	list<int>q;
	memset(dis,-0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	vis[s]=dis[s]=0,now[s]=head[s];
	q.push_back(s);
	while(!q.empty()){
		int u=q.front();
		q.pop_front();
		vis[u]=0;
		for(int i=head[u];i;i=nxt[i]){
			now[to[i]]=head[to[i]];
			if(!val[i]) continue;
			if(dis[to[i]]<dis[u]+cost[i]){
				dis[to[i]]=dis[u]+cost[i];
				cnt[to[i]]=cnt[u]+1;
				if(vis[to[i]]) continue;
				vis[to[i]]=1;
				if(dis[to[i]]<dis[q.empty() ? 0 :q.front()]) q.push_front(to[i]);
				else q.push_back(to[i]);
			}
		}
	}
	memset(vis,0,sizeof vis);
	return dis[t]>dis[0]/2;
}
int dinic(int x,int flow){
	vis[x]=1;
	if(x==t) return flow;
	int rest=flow;
	for(int i=now[x];i && rest;i=nxt[i]){
		now[x]=i;
		if(dis[to[i]]!=dis[x]+cost[i] || !val[i] || vis[to[i]]) continue;
		int v=dinic(to[i],min(rest,val[i]));
		if(!v) dis[to[i]]=dis[0];
		val[i]-=v,val[i^1]+=v,maxcost+=cost[i]*v;
		rest-=v;
	}
	return flow-rest;
}
namespace Input{
	int a[210][210];
	void main() {
		for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
	}
}
int get(int x,int y,int k){
	return (x-1)*m+y+k*n*m;
}
signed main() {
	ios::sync_with_stdio(0);
	cin>>n>>m;
	s=n*m+1,t=n*m;
	Input::main();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			add(get(i,j,0),get(i,j,1),1,Input::a[i][j]),add(get(i,j,1),get(i,j,0),0,-Input::a[i][j]);
			if(i<n) add(get(i,j,1),get(i+1,j,0),1,0),add(get(i+1,j,0),get(i,j,1),0,0);
			if(j<m) add(get(i,j,1),get(i,j+1,0),1,0),add(get(i,j+1,0),get(i,j,1),0,0);
		}
	}
	int flow=0;
	while(spfa()) while(flow=dinic(s,1e18)) maxflow+=flow;
	cout<<maxcost;
	return 0;
}

此代码能过 ouuan 的大教室中传纸条。

题解：P1006 [NOIP 2008 提高组] 传纸条

文章操作

相关推荐

评论

题解：P1006 [NOIP 2008 提高组] 传纸条