游客 注册 | 登录
中文 | En

1926 - 城墙

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

有一个国家，城市之间都用城墙连接起来，每个城市里有一个或者没有打高尔夫的高手。现在这些高尔夫高手打算挑一个空地r一决高下（空地就是由城墙围起来的地方）。由于国家管制，所属i城市的人不能去其他任意的城市。因此有些人要去空地r不得不翻越一些城墙，当然翻墙是件很困难的事情，所以尽量能少翻墙。现在问你挑哪个区域来做为他们比赛的地点，使得他们翻过墙的总和最小。


Figure1：输入样例情况图
Figure2：翻越城墙数最小的一种情况

题目输入

第一行：M 表示空地数（2 <= M <= 200）
第二行：N 表示城市数目（3 <= N <= 250）
第三行：L 表示高尔夫高手人数（1 <= L <= 30）
第四行：L个数字，依次表示L位高尔夫高手所在城市编号
接下来2*M行：每两行对应一个空地，第一行表示空地周围的城市数，第二行表示城市的代号，前M-1个按城市编号按顺时针顺序输出，第M个按逆时针输出。

题目输出

输出一个整数：总共需要翻越的城墙数的最小值

输入/输出样例

输入格式

10
10
3
3 6 9 
3
1 2 3 
3
1 3 7 
4
2 4 7 3 
3
4 6 7 
3
4 8 6 
3
6 8 7 
3
4 5 8 
4
7 8 10 9 
3
5 10 8 
7
7 9 10 5 4 2 1

输出格式

2

C++解答

/*其实这个题就是把点当成面来给了，对于某一个区域，把他当成一个点，
和他相邻的区域与他之间有一条权为1的边，
*/
#include<stdio.h>
#include<string.h>
#define Max 210
#define INF 10000000
#define M 210
#define N 260

bool map[M][M];

struct Area
{
	int town;    //在该区域边上城镇数
	int turn[N]; //这些城镇依次是turn[n];
	int f[N];    //f[i]记i是turn[n]的第f[i]个数
}area[M];

bool check(int x, int y)
{
	int i, a, b, t;
	bool yes = 0;
	for(i = 0; i < area[y].town; i++){
		a = area[y].turn[i]; 
		b = area[y].turn[(i+1)%area[y].town];		
		if(area[x].f[a] != -1 && area[x].f[b] != -1)
		{
			t = area[x].f[a]-area[x].f[b];
			if(t == -1 || t == 1 || t == area[x].town-1 || t == 1-area[x].town)
			{	yes = 1; break; }
		}
	}
	return yes;
}

int A[Max][Max];
void Floyd(int n)
{
	int i, j, k;
	for(i = 0; i < n; i++){
		for(j = 0; j < n; j++){
			if(i != j && !map[i][j])
				A[i][j] = INF;
			else A[i][j] = map[i][j];
		}
	}
	for(k = 0; k < n; k++){
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				if(A[i][j] > A[i][k]+A[k][j])
					A[i][j] = A[i][k]+A[k][j];
	}
}

int main()
{
	int i, j, m, n, l, man[40];
	int town[N][N], num[N];
		//freopen("walls.in", "r", stdin);
	//freopen("walls.out", "w", stdout);
	scanf("%d", &m);
		scanf("%d", &n);
		scanf("%d", &l);
		for(i = 0; i < l; i++)
			scanf("%d", &man[i]);

		memset(map, 0, sizeof(map));
		memset(num, 0, sizeof(num));
		for(i = 0; i < m; i++){
			scanf("%d", &area[i].town);	
			memset(area[i].f, -1, sizeof(area[i].f));
			for(j = 0; j < area[i].town; j++){
				scanf("%d", &area[i].turn[j]);
				area[i].f[area[i].turn[j]] = j;
				town[area[i].turn[j]][num[area[i].turn[j]]] = i;
				num[area[i].turn[j]]++;
			}
			for(j = 0; j < i; j++)
				map[i][j] = map[j][i] = check(i, j);
		}
		Floyd(m);
		int minsum, sum, min, k;
		for(i = 0; i < m; i++){
			sum = 0;
			for(j = 0; j < l; j++){
				min = A[town[man[j]][0]][i];
				for(k = 1; k < num[man[j]]; k++){
					if(min > A[town[man[j]][k]][i])
						min = A[town[man[j]][k]][i];
				}
				sum += min;
			}
			if(!i) minsum = sum;
			else if(minsum > sum)
				minsum = sum;
		}
		printf("%d\n", minsum);

//	}
	return 0;
}
请先登陆