NOI 2004 曼哈顿

一开始一直在想网络流，没想到是动态规划。首先观察到M很小，于是我们可以枚举每行的方向，也不过2^10=1024。当确定了每行的方向，接下来就需要仔细思考了。

对于每一对要求的顶点A,B，可以根据A,B的相对位置分类。假设横轴上B在A的X方向，纵轴上B在A的Y方向。

如果A，B就是同一点，显然满足。
如果A，B在同一行，必须保证该行的方向为Y。
如果A，B在同一列，则该列方向应为X。
如果A，B不在同行列，则需要判断AB所在行方向。
- 如果A，B所在行的方向均为Y，此时需要在AB之间有一条方向为X的列。
如果A所在行方向为Y，B所在行方向为Y的反方向，此时必须B所在列方向为X。
如果A所在行方向为Y的反方向，B所在行方向为Y，此时必须A所在列方向为X。
如果A，B所在行的方向均为Y的反方向，则必须保证A，B所在行之间有一行方向为Y，且A，B所在列方向都必须为X。

根据上述七种情况，可以把问题抽象成有一些区间，假设要求向上的列的区间为正区间，要求向下的列的区间为反区间，要求修改一些列的方向，使之满足所有正区间和反区间，且总费用最小。

进一步分析，如果一个区间a包含另一个区间b，则当b满足时a一定满足，且费用不会增大，于是可以把a剔除。排序后扫描一下去掉所有这类区间，剩下的区间的两个端点一定是都分别单调递增的，而且区间的个数是O(N)级别的。

最后一步是动态规划了，设定状态F[i][j][k]为前i列中，正区间满足了j个，反区间满足了k个时最小的费用。V[i][0]为把第i列修改为向上的费用，V[i][1]为把第i列修改为向下的费用。

状态转移方程为

F[i][j][k]=Min
{
	F[i-1][j][k],
	F[i-1][a][k] + V[i][0], (a为右端点小于i的最右边的正区间)
	F[i-1][j][b] + V[i][1], (b为右端点小于i的最右边的反区间)
}

状态转移中的a，b可以预处理出来。为了输出方案，需要记录决策。最终总的时间复杂度为O(2^M*N^3)。细节颇多，非常容易错，我写了260行程序。

其实费用流也可以建模的，只是比较复杂，而且时间复杂度太高。

/* 
 * Problem: NOI2004 manhattan
 * Author: Guo Jiabao
 * Time: 2009.5.29 10:35
 * State: Solved
 * Memo: 枚举 + 动态规划
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXM=11,MAXN=101,MAXK=101,INF=0x7FFFFFFF/2;
struct ppoint
{
	int x1,y1,x2,y2;
}P[MAXK];
struct segment
{
	int a,b;
}S[2][MAXK*2],St[2][MAXK*2];
struct path
{
	int i,j,k,a;
} Ft[MAXN][MAXN][MAXN];
int M,N,K,Ans,C[2],E[2];
int Dx[MAXM],Dy[MAXN],Vx[MAXM],Vy[MAXN],Tx[MAXM],Ty[MAXN],Ax[MAXM],Ay[MAXN],Left[2][MAXN];
int F[MAXN][MAXN][MAXN];
void init()
{
	int i,c;
	freopen("manhattan.in","r",stdin);
	freopen("manhattan.out","w",stdout);
	scanf("%d%d",&M,&N);
	while ((c=getchar())==10 || c==13); ungetc(c,stdin);
	for (i=1;i<=M;i++)
		Dx[i]=getchar()=='E';
	while ((c=getchar())==10 || c==13); ungetc(c,stdin);
	for (i=1;i<=N;i++)
		Dy[i]=getchar()=='S';
	for (i=1;i<=M;i++)
		scanf("%d",&Vx[i]);
	for (i=1;i<=N;i++)
		scanf("%d",&Vy[i]);
	scanf("%d",&K);
	for (i=1;i<=K;i++)
		scanf("%d%d%d%d",&P[i].x1,&P[i].y1,&P[i].x2,&P[i].y2);
	Ans=INF;
	S[0][0].a=S[0][0].b=S[1][0].a=S[1][0].b=0;
}
inline int cmp(const void *a,const void *b)
{
	if (((segment *)a)->b < ((segment *)b)->b) return -1;
	if (((segment *)a)->b > ((segment *)b)->b) return 1;
	return -(((segment *)a)->a - ((segment *)b)->a);
}
inline int Cost(int i,int x)
{
	if (Dy[i]==x) return 0;
	return Vy[i];
}
int dynamic()
{
	int i,j,k,a,A=INF,v,ti,tj,tk;
	for (i=0;i<=1;i++)
	{
		E[i]=0;
		if (!C[i]) continue;
		qsort(St[i]+1,C[i],sizeof(St[0][0]),cmp);
		S[i][1]=St[i][1];
		E[i]=1;
		for (k=1,j=2;j<=C[i];j++)
		{
			if (St[i][j].a > St[i][k].a)
			{
				k=j;
				S[i][++E[i]]=St[i][j];
			}
		}
		for (k=1,j=1;j<=E[i];j++)
		{
			for (;k<=S[i][j].b;k++)
				Left[i][k]=j-1;
		}
		for (;k<=N;k++)
			Left[i][k]=E[i];
	}
	for (i=0;i<=N;i++)
	{
		for (j=0;j<=E[0];j++)
			for (k=0;k<=E[1];k++)
				F[i][j][k]=INF;
		Ty[i]=-1;
	}
	F[0][0][0]=0;
	for (i=1;i<=N;i++)
	{
		for (j=0;j<=E[0];j++)
		{
			for (k=0;k<=E[1];k++)
			{
				if (j==0 && k==0)
				{
					F[i][j][k]=0;
					Ft[i][j][k].i=0;
					Ft[i][j][k].a=-1;
				}
				else
				{
					F[i][j][k]=F[i-1][j][k];
					Ft[i][j][k].i=i-1;
					Ft[i][j][k].j=j;
					Ft[i][j][k].k=k;
					Ft[i][j][k].a=-1;
					if (j>0 && i>=S[0][j].a && i<=S[0][j].b)
					{
						a=Left[0][i];
						v=F[i-1][a][k] + Cost(i,0);
						if (v < F[i][j][k])
						{
							F[i][j][k]=v;
							Ft[i][j][k].i=i-1;
							Ft[i][j][k].j=a;
							Ft[i][j][k].k=k;
							Ft[i][j][k].a=0;
						}
					}
					if (k>0 && i>=S[1][k].a && i<=S[1][k].b)
					{
						a=Left[1][i];
						v=F[i-1][j][a] + Cost(i,1);
						if (v < F[i][j][k])
						{
							F[i][j][k]=v;
							Ft[i][j][k].i=i-1;
							Ft[i][j][k].j=j;
							Ft[i][j][k].k=a;
							Ft[i][j][k].a=1;
						}
					}
				}
				if (j==E[0] && k==E[1] && F[i][j][k]<A)
				{
					A=F[i][j][k];
					ti=i;
				}
			}
		}
	}
	if (A!=INF)
	{
		j=E[0];k=E[1];
		for (i=ti;i;i=ti,j=tj,k=tk)
		{
			Ty[i] = Ft[i][j][k].a;
			ti=Ft[i][j][k].i;
			tj=Ft[i][j][k].j;
			tk=Ft[i][j][k].k;
		}
	}
	return A;
}
void addseg(int a,int b,int x)
{
	int c=a;
	if (a>b)
		a=b,b=c;
	St[x][++C[x]].a=a;
	St[x][ C[x] ].b=b;
}
void solve()
{
	int NewAns=0,i,j,k,X,Y,a,b;
	for (i=1;i<=M;i++)
	{
		if (Dx[i]!=Tx[i])
			NewAns += Vx[i];
	}
	C[0]=C[1]=0;
	for (k=1;k<=K;k++)
	{
		X = P[k].x2 > P[k].x1;
		Y = P[k].y2 > P[k].y1;
		if (P[k].x1 == P[k].x2 && P[k].y1==P[k].y2)
			continue;
		else if (P[k].x1 == P[k].x2)
		{
			if (Tx[ P[k].x1 ] != Y)
				return;
		}
		else if (P[k].y1==P[k].y2)
			addseg(P[k].y1,P[k].y1,X);
		else if ( Tx[ P[k].x1 ] == Y && Tx[ P[k].x2 ] == Y)
			addseg(P[k].y1,P[k].y2,X);
		else if ( Tx[ P[k].x1 ] == Y && Tx[ P[k].x2 ] != Y )
			addseg(P[k].y2,P[k].y2,X);
		else if ( Tx[ P[k].x1 ] != Y && Tx[ P[k].x2 ] == Y )
			addseg(P[k].y1,P[k].y1,X);
		else
		{
			a=P[k].x1; b=P[k].x2;
			if (a>b)
				b=P[k].x1, a=P[k].x2;
			for (j=a+1;j<b;j++)
				if (Tx[j] == Y)
					break;
			if (j==b)
				return;
			addseg(P[k].y1,P[k].y1,X);
			addseg(P[k].y2,P[k].y2,X);
		}
	}
	NewAns += dynamic();
	if (NewAns < Ans)
	{
		for (i=1;i<=M;i++)
			Ax[i]=Tx[i];
		for (i=1;i<=N;i++)
		{
			if (Ty[i]!=-1)
				Ay[i]=Ty[i];
			else
				Ay[i]=Dy[i];
		}
		Ans = NewAns;
	}
}
void DFS(int k)
{
	if (k>M)
	{
		solve();
		return;
	}
	Tx[k]=1;
	DFS(k+1);
	Tx[k]=0;
	DFS(k+1);
}
void print()
{
	if (Ans==INF)
		printf("impossiblen");
	else
	{
		printf("possiblen");
		printf("%dn",Ans);
		int i;
		for (i=1;i<=M;i++)
			putchar(Ax[i]?'E':'W');
		putchar('n');
		for (i=1;i<=N;i++)
			putchar(Ay[i]?'S':'N');
		putchar('n');
	}
}
int main()
{
	init();
	DFS(1);
	print();

	return 0;
}

<h2><span class="mw-headline">曼哈顿 </span></h2>

【问题描述】

P城是M国的著名旅游城市。在市长G先生的治理下，人民安居乐业，城市欣欣向荣。然而，G市长并没有被自己的政绩冲昏头脑，他清醒地意识到城市的治理还存在着一些问题，其中之一就是交通问题。

P城有m条横向街道和n条纵向街道，横向街道横贯东西，纵向街道纵穿南北，构成了P城整齐的交通网络（如图1所示）。

<a class="image" title="Image:Manhattan.gif" href="http://www.ruvtex.cn/wiki/Image:Manhattan.gif"><img src="http://www.ruvtex.cn/mw/images/4/43/Manhattan.gif" alt="Image:Manhattan.gif" width="564" height="387" /></a>

图1

由于街道狭窄，每条街道都只允许单向行驶，单向行驶的方向是事先设定好了的。一条横向街道的行驶方向只能是向东或者向西，一条纵向街道的行驶方向只能是向南或者向北，逆向行驶是绝对禁止的。

这项限制给交通带来了巨大的不便。如图1，很多游人希望从宾馆前往购物中心，但限于街道的行驶方向，他们不得不绕一个大圈才能够到达。

这个问题一直困扰着G市长，每天他都会收到不少游人的来信，抱怨P城不合理的交通设计。但由于街道数目过多，他和他的部下始终不能解决这个问题……

令人高兴的是这个问题不久就可能得以解决。因为最近他们以重金聘请了著名的交通规划大师B先生，请他对P城的交通进行有效合理的改造。

B先生知道不能通过拓宽街道的方法解决问题，因为这样势必影响到街道两旁的旅游景点，这是大家都不希望看到的。于是他准备重新设计街道的行驶方向（整条街道的行驶方向），使之尽可能满足大家的要求。

B先生先把P城的街道编号，横向街道由北向南编号为1，2，……，m，纵向街道由西向东编号为1，2，……，n。这样任何一个十字路口的位 置都可以用一对正整数来表示，第一个数是该路口所在的横向街道的编号，第二个数是它所在的纵向街道的编号，这对整数被称为该十字路口的坐标。比如图1中宾 馆所在的十字路口的坐标是(2,3)。

经过长期调查，他整理出了游人们提得相对集中的一些要求。每条要求都可以写成如下的形式：从一个十字路口到另一个十字路口的最短路径的长 度必须等于它们之间的曼哈顿距离。所谓曼哈顿距离是指两个十字路口在东西方向上的距离加上在南北方向上的距离，坐标分别为(x1,y1)和(x2,y2) 的两个十字路口之间的曼哈顿距离为|x1-x2|+|y1-y2|。

好了，B先生已经知道了P城目前所有街道的行驶方向和游人们提得相对集中的要求，他能不能重新设计街道的行驶方向，使之满足所有要求呢？

另外，改变每条街道的行驶方向都有一定的工作量，工作量的大小因道路而异。B先生不仅想找到一个可行的改造计划，而且还希望这个计划的总工作量尽可能小。你能帮帮他吗？
【输入文件】

输入文件的第一行有两个正整数m和n，分别表示横向街道和纵向街道的数目。

第二行是一个长度为m的字符串，由北向南列出了m条横向街道改造前的行驶方向。E表示向东，W表示向西。

第三行是一个长度为n的字符串，由西向东列出了n条纵向街道改造前的行驶方向。S表示向南，N表示向北。

第四行有m个非负整数，由北向南列出了改变每条横向街道的行驶方向的工作量。

第五行有n个非负整数，由西向东列出了改变每条纵向街道的行驶方向的工作量。

第六行是一个正整数k，表示游人们提得相对集中的要求的数目。

接下来的k行，每行有四个正整数x1，y1，x2，y2，表示一条要求。这条要求的内容是希望从坐标为(x1,y1)的十字路口到坐标为(x2,y2)的十字路口的最短路径的长度等于这两个路口之间的曼哈顿距离。
【输出文件】

第一行是一个字符串，“possible”或者“impossible”（引号不输出）。输出“possible”表示可以通过改变街道的行驶方向满足输入数据中的所有要求，输出“impossible”表示无论怎么设计都不可能满足输入数据中的所有要求。

如果在第一行输出的是“possible”的话，在第二行输出一个整数，表示最小的总工作量，在第三行输出一个长度为m的字符串，由北向南 列出改造后的m条横向街道的行驶方向，E表示向东，W表示向西，在第四行输出一个长度为n的字符串，由西向东列出改造后的n条纵向街道的行驶方向， S表示向南，N表示向北。
【约定】

M<=10
N<=100
K<=100
改变一条街道的行驶方向的工作量不超过10000

【样例输入】
```
2 3
  WE
  NNS
  3 9
  1 4 2
  2
  1 3 2 1
  2 3 2 2
```
【样例输出】
```
possible
  9
  WW
  NNS
```
【评分方法】
如果你的输出文件的第一行是“impossible”，
如果确实无解，则该测试点满分。
如果实际有解，则该测试点0分。
如果你的输出文件的第一行是“possible”，
如果你的程序输出的方案不可行，则该测试点0分。
如果你的程序输出的总工作量与实际总工作量不一致，则该测试点0分。
如果你的程序输出的方案可行，但总工作量不是最小的，则该测试点4分。
如果你的程序输出的方案可行，且总工作量最小，则该测试点满分。

上次修改时间 2017-05-22

相关日志