4.1.3 Fence Loops 篱笆回路

4.1.3 Fence Loops 篱笆回路

时间: 1ms        内存:64M

描述:

农夫布朗的牧场上的篱笆已经失去控制了。它们分成了1~200英尺长的线段。只有在线段的端点处才能连接两个线段,有时给定的一个端点上会有两个以上的篱笆。结果篱笆形成了一张网分割了布朗的牧场。布朗想将牧场恢复原样,出于这个考虑,他首先得知道牧场上哪一块区域的周长最小。
布朗将他的每段篱笆从1到N进行了标号(N=线段的总数)。他知道每段篱笆的有如下属性:

该段篱笆的长度
该段篱笆的一端所连接的另一段篱笆的标号
该段篱笆的另一端所连接的另一段篱笆的标号
幸运的是,没有篱笆连接它自身。
对于一组有关篱笆如何分割牧场的数据,写一个程序来计算出所有分割出的区域中最小的周长。
例如,标号1~10的篱笆由下图的形式组成(下面的数字是篱笆的标号):
 

           1
   +---------------+
   |\             /|
  2| \7          / |
   |  \         /  |
   +---+       /   |6
   | 8  \     /10  |
  3|     \9  /     |
   |      \ /      |
   +-------+-------+
       4       5

上图中周长最小的区域是由2,7,8号篱笆形成的。

输入:

第1行: N (1 <= N <= 100) 第2行到第3*N+1行: 每三行为一组,共N组信息: 每组信息的第1行有4个整数: s, 这段篱笆的标号(1 <= s <= N); Ls, the这段篱笆的长度 (1 <= Ls <= 255); N1s (1 <= N1s <= 8) 与本段篱笆的一端所相邻的篱笆的数量; and N2s与本段篱笆的另一端所相邻的篱笆的数量。 (1 <= N2s <= 8). 每组信息的的第2行有 N1s个整数, 分别描述与本段篱笆的一端所相邻的篱笆的标号。 每组信息的的第3行有N2s个整数, 分别描述与本段篱笆的另一端所相邻的篱笆的标号。

输出:

输出的内容为单独的一行,用一个整数来表示最小的周长。

示例输入:

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

示例输出:

12

提示:

参考答案(内存最优[856]):

#include <stdio.h>
#include <string.h>

typedef struct{
	int leng;
	int link[2][12];
}board;

board b[103];
int map[105][105];
int cnt;
int min;
int sum[105];
int num[105];
bool vis[105];

int seach(int d[], int k)
{
	int nodevalue = 0;
	int t = 1;
	do{
		int v = d[t];
		int i;
		for (i=1; b[v].link[0][i] && !nodevalue; i++)
			if (b[v].link[0][i] == k && b[v].link[0][0])
			{	
				nodevalue = b[v].link[0][0];
			}
		for (i=1; b[v].link[1][i] && !nodevalue; i++)
			if (b[v].link[1][i] == k && b[v].link[1][0])
				nodevalue = b[v].link[1][0];
	}while (d[++t]);
	nodevalue = nodevalue?nodevalue:++cnt;
	for (int i=1; d[i]; i++)
	{
		if (b[d[i]].link[0][0] != nodevalue && b[d[i]].link[1][0] != nodevalue)
			b[d[i]].link[0][0] = nodevalue;
	}
	return nodevalue;
}

void dfs(int ti, int s, int cntnum)
{
	int i;
	num[ti] = cntnum;
	sum[ti] = s;
	vis[ti] = 1;
	for (i=1; i<=cnt; i++)
		if (map[ti][i] <= 255)
		{
			if (sum[i])
			{
				if (s - sum[i] + map[ti][i] < min && num[ti] - num[i] > 1)
					min = s - sum[i] + map[ti][i];
			}
			else
			{
				dfs(i, s + map[ti][i], cntnum + 1);
			}
		}
	num[ti] = 0;
	sum[ti] = 0;
}

int main()
{
	int n;
	while (scanf("%d", &n) == 1)
	{
		memset(map, 1, sizeof(map));
		min = 9999999;
		int i, j;
		for (i=1; i<=n; i++)
		{
			int t, l, r;
			int nodevalue1, nodevalue0;
			scanf("%d", &t);
			scanf("%d %d %d", &b[t].leng, &l, &r);
			for (j=1; j<=l; j++)
			{
				scanf("%d", &b[t].link[0][j]);
			}
			b[t].link[0][0] = nodevalue0 = seach(b[t].link[0], t);
			for (j=1; j<=r; j++)
			{
				scanf("%d", &b[t].link[1][j]);
			}
			b[t].link[1][0] = nodevalue1 = seach(b[t].link[1], t);
			map[nodevalue0][nodevalue1] = map[nodevalue1][nodevalue0] = b[t].leng;
		}
		for (i=1; i<=cnt; i++)
			if (!vis[i])
				dfs(i, 0, 1);
		printf("%d\n", min);
	}
	return 0;
}

参考答案(时间最优[4]):

#include <stdio.h>
#include <string.h>

typedef struct{
	int leng;
	int link[2][12];
}board;

board b[103];
int map[105][105];
int cnt;
int min;
int sum[105];
int num[105];
bool vis[105];

int seach(int d[], int k)
{
	int nodevalue = 0;
	int t = 1;
	do{
		int v = d[t];
		int i;
		for (i=1; b[v].link[0][i] && !nodevalue; i++)
			if (b[v].link[0][i] == k && b[v].link[0][0])
			{	
				nodevalue = b[v].link[0][0];
			}
		for (i=1; b[v].link[1][i] && !nodevalue; i++)
			if (b[v].link[1][i] == k && b[v].link[1][0])
				nodevalue = b[v].link[1][0];
	}while (d[++t]);
	nodevalue = nodevalue?nodevalue:++cnt;
	for (int i=1; d[i]; i++)
	{
		if (b[d[i]].link[0][0] != nodevalue && b[d[i]].link[1][0] != nodevalue)
			b[d[i]].link[0][0] = nodevalue;
	}
	return nodevalue;
}

void dfs(int ti, int s, int cntnum)
{
	int i;
	num[ti] = cntnum;
	sum[ti] = s;
	vis[ti] = 1;
	for (i=1; i<=cnt; i++)
		if (map[ti][i] <= 255)
		{
			if (sum[i])
			{
				if (s - sum[i] + map[ti][i] < min && num[ti] - num[i] > 1)
					min = s - sum[i] + map[ti][i];
			}
			else
			{
				dfs(i, s + map[ti][i], cntnum + 1);
			}
		}
	num[ti] = 0;
	sum[ti] = 0;
}

int main()
{
	int n;
	while (scanf("%d", &n) == 1)
	{
		memset(map, 1, sizeof(map));
		min = 9999999;
		int i, j;
		for (i=1; i<=n; i++)
		{
			int t, l, r;
			int nodevalue1, nodevalue0;
			scanf("%d", &t);
			scanf("%d %d %d", &b[t].leng, &l, &r);
			for (j=1; j<=l; j++)
			{
				scanf("%d", &b[t].link[0][j]);
			}
			b[t].link[0][0] = nodevalue0 = seach(b[t].link[0], t);
			for (j=1; j<=r; j++)
			{
				scanf("%d", &b[t].link[1][j]);
			}
			b[t].link[1][0] = nodevalue1 = seach(b[t].link[1], t);
			map[nodevalue0][nodevalue1] = map[nodevalue1][nodevalue0] = b[t].leng;
		}
		for (i=1; i<=cnt; i++)
			if (!vis[i])
				dfs(i, 0, 1);
		printf("%d\n", min);
	}
	return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注