首页 > 代码库 > USACO 4.1 Fence Loops（Floyd求最小环）

USACO 4.1 Fence Loops（Floyd求最小环）

2024-09-01 02:09:44   217人阅读

Fence Loops

The fences that surround Farmer Brown‘s collection of pastures have gotten out of control. They are made up of straight segments from 1 through 200 feet long that join together only at their endpoints though sometimes more than two fences join together at a given endpoint. The result is a web of fences enclosing his pastures. Farmer Brown wants to start to straighten things out. In particular, he wants to know which of the pastures has the smallest perimeter.

Farmer Brown has numbered his fence segments from 1 to N (N = the total number of segments). He knows the following about each fence segment:

  • the length of the segment
  • the segments which connect to it at one end
  • the segments which connect to it at the other end.

Happily, no fence connects to itself.

Given a list of fence segments that represents a set of surrounded pastures, write a program to compute the smallest perimeter of any pasture. As an example, consider a pasture arrangement, with fences numbered 1 to 10 that looks like this one (the numbers are fence ID numbers):

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

The pasture with the smallest perimeter is the one that is enclosed by fence segments 2, 7, and 8.

PROGRAM NAME: fence6

INPUT FORMAT

Line 1: N (1 <= N <= 100)
Line 2..3*N+1:

N sets of three line records:

  • The first line of each record contains four integers: s, the segment number (1 <= s <= N); Ls, the length of the segment (1 <= Ls <= 255); N1s (1 <= N1s <= 8) the number of items on the subsequent line; and N2sthe number of items on the line after that (1 <= N2s <= 8).
  • The second line of the record contains N1 integers, each representing a connected line segment on one end of the fence.
  • The third line of the record contains N2 integers, each representing a connected line segment on the other end of the fence.

SAMPLE INPUT (file fence6.in)

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

OUTPUT FORMAT

The output file should contain a single line with a single integer that represents the shortest surrounded perimeter.

SAMPLE OUTPUT (file fence6.out)

12

 ——————————————————————

听说是应该拿floyd写最小环，但是始终没想出来怎么写，结果发现好简单啊……果然还是自己蒟蒻

回归floyd的三维形式g[k,i,j]也就是用前k个点更新了i,j，然后我们发现我们求的环就是

i到j不包括k的最短路+i到k距离+k到j距离

我们更新一次floyd二维矩阵存储的就是g[k-1,i,j]，然后我们得到的k点是新的，未被使用过，这样就可以做了

【这道题图给的形式真是好恶心啊……】

 1 /*
 2 ID: ivorysi
 3 PROG: fence6
 4 LANG: C++
 5 */
 6 #include <iostream>
 7 #include <cstdio>
 8 #include <cstring>
 9 #include <algorithm>
10 #include <queue>
11 #include <set>
12 #include <vector>
13 #include <string.h>
14 #define siji(i,x,y) for(int i=(x);i<=(y);++i)
15 #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
16 #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
17 #define sigongzi(j,x,y) for(int j=(x);j>(y);--j)
18 #define inf 0x1f1f1f1f
19 #define ivorysi
20 #define mo 97797977
21 #define ha 974711
22 #define ba 47
23 #define fi first
24 #define se second
25 #define pii pair<int,int>
26 using namespace std;
27 typedef long long ll;
28 int s,len[105],num[105][4],cnt,a1[105],a2[105],use[105];
29 int g[205][205],f[205][205];
30 int n,t1,t2,ans;
31 void solve(){
32     scanf("%d",&n);
33     siji(i,1,n) {
34         scanf("%d",&s);
35         scanf("%d",&len[s]);
36         scanf("%d%d",&t1,&t2);
37         
38         bool f1=1,f2=1;
39         siji(j,1,t1) {
40             scanf("%d",&a1[j]);
41             if(use[a1[j]]) f1=0;
42         }
43         siji(j,1,t2) {
44             scanf("%d",&a2[j]);
45             if(use[a2[j]]) f2=0;
46         }
47         if(num[s][0]>=2)continue;
48         if(f1) {
49             num[s][++num[s][0]]=++cnt;
50             siji(j,1,t1) {
51                 num[a1[j]][++num[a1[j]][0]]=cnt;
52             }
53         }
54         if(f2) {
55             num[s][++num[s][0]]=++cnt;
56             siji(j,1,t2) {
57                 num[a2[j]][++num[a2[j]][0]]=cnt;
58             }
59         }
60         use[s]=1;
61     }
62     memset(g,inf,sizeof(g));
63     memset(f,inf,sizeof(f));
64     siji(i,1,n) {
65         g[num[i][1]][num[i][2]]=g[num[i][2]][num[i][1]]=len[i];
66         f[num[i][1]][num[i][2]]=f[num[i][2]][num[i][1]]=len[i];
67     }
68     siji(i,1,cnt) {g[i][i]=0;f[i][i]=0;}
69     ans=inf;
70     siji(k,1,cnt) {
71         xiaosiji(i,1,k) {//因为不能用k点所以是<k
72             xiaosiji(j,i+1,k) {
73                 ans=min(ans,g[i][j]+f[i][k]+f[k][j]);
74             }
75         }
76         siji(i,1,cnt) {
77             siji(j,1,cnt) {
78                 g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
79             }
80         }
81     }
82 
83     printf("%d\n",ans);
84 }
85 int main(int argc, char const *argv[])
86 {
87 #ifdef ivorysi
88     freopen("fence6.in","r",stdin);
89     freopen("fence6.out","w",stdout);
90 #else
91     freopen("f1.in","r",stdin);
92 #endif
93     solve();
94 }

 

USACO 4.1 Fence Loops（Floyd求最小环）


联系
我们