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;
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。