# 4.1.3 Fence Loops 篱笆回路

4.1.3 Fence Loops 篱笆回路

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

``````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
``````

``````#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;
}``````

``````#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;
}``````