NOI 2004 曼哈頓

本文正體字版由OpenCC轉換

一開始一直在想網絡流，沒想到是動態規劃。首先觀察到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

相關日誌