📄 usaco 4_1_3 fence loops 题解_leokan的blog.mht
字号:
<DIV class=3Dcnt>
<H2>USACO 4.1.3 Fence Loops</H2>
<DIV class=3Dt_msgfont>Fence Loops<BR><BR>The fences that surround =
Farmer=20
Brown's collection of pastures have gotten out of control. They =
are made=20
up of straight segments from 1 through 200 feet long that join =
together=20
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=20
pastures. Farmer Brown wants to start to straighten things out. In =
particular, he wants to know which of the pastures has the =
smallest=20
perimeter. <BR><BR>Farmer Brown has numbered his fence segments =
from 1 to=20
N (N =3D the total number of segments). He knows the following =
about each=20
fence segment: <BR><BR>the length of the segment <BR>the segments =
which=20
connect to it at one end <BR>the segments which connect to it at =
the other=20
end. <BR>Happily, no fence connects to itself. <BR>Given a list of =
fence=20
segments that represents a set of surrounded pastures, write a =
program to=20
compute the smallest perimeter of any pasture. As an example, =
consider a=20
pasture arrangement, with fences numbered 1 to 10 that looks like =
this one=20
(the numbers are fence ID numbers): <BR><BR> =
=20
1<BR>+---------------+<BR>|\ =
=20
/|<BR> 2| \7 /=20
|<BR>| \ / =
|<BR>+---+=20
/ |6<BR>| 8 \ =
/10 =20
|<BR> 3| \9 /=20
|<BR>| \ / =20
|<BR>+-------+-------+<BR> 4 5<BR><BR>The =
pasture=20
with the smallest perimeter is the one that is enclosed by fence =
segments=20
2, 7, and 8. <BR><BR>PROGRAM NAME: fence6<BR>INPUT FORMAT<BR>Line=20
1: N (1 <=3D N <=3D 100) <BR>Line =
2..3*N+1: N=20
sets of three line records: <BR><BR>The first line of each record =
contains=20
four integers: s, the segment number (1 <=3D s <=3D N); Ls, =
the length=20
of the segment (1 <=3D Ls <=3D 255); N1s (1 <=3D N1s =
<=3D 8) the=20
number of items on the subsequent line; and N2sthe number of items =
on the=20
line after that (1 <=3D N2s <=3D 8). <BR>The second line of =
the record=20
contains N1 integers, each representing a connected line segment =
on one=20
end of the fence. <BR>The third line of the record contains N2 =
integers,=20
each representing a connected line segment on the other end of the =
fence.=20
<BR><BR><BR>SAMPLE INPUT (file fence6.in) <BR>10<BR>1 16 2 2<BR>2 =
7<BR>10=20
6<BR>2 3 2 2<BR>1 7<BR>8 3<BR>3 3 2 1<BR>8 2<BR>4<BR>4 8 1 =
3<BR>3<BR>9 10=20
5<BR>5 8 3 1<BR>9 10 4<BR>6<BR>6 6 1 2 <BR>5 <BR>1 10<BR>7 5 2 2 =
<BR>1=20
2<BR>8 9<BR>8 4 2 2<BR>2 3<BR>7 9<BR>9 5 2 3<BR>7 8<BR>4 5 =
10<BR>10 10 2=20
3<BR>1 6<BR>4 9 5<BR><BR>OUTPUT FORMAT<BR>The output file should =
contain a=20
single line with a single integer that represents the shortest =
surrounded=20
perimeter. <BR>SAMPLE OUTPUT (file =
fence6.out)<BR>12<BR><BR><BR><BR>Fence=20
Loops<BR><BR>=C0=E9=B0=CA=BB=D8=C2=B7<BR><BR>=D2=EB by=20
=
Zen<BR><BR>=C5=A9=B7=F2=B2=BC=C0=CA=B5=C4=C4=C1=B3=A1=C9=CF=B5=C4=C0=E9=B0=
=CA=D2=D1=BE=AD=CA=A7=C8=A5=BF=D8=D6=C6=C1=CB=A1=A3=CB=FC=C3=C7=B7=D6=B3=C9=
=C1=CB1~200=D3=A2=B3=DF=B3=A4=B5=C4=CF=DF=B6=CE=A1=A3=D6=BB=D3=D0=D4=DA=CF=
=DF=B6=CE=B5=C4=B6=CB=B5=E3=B4=A6=B2=C5=C4=DC=C1=AC=BD=D3=C1=BD=B8=F6=CF=DF=
=B6=CE=A3=AC=D3=D0=CA=B1=B8=F8=B6=A8=B5=C4=D2=BB=B8=F6=B6=CB=B5=E3=C9=CF=BB=
=E1=D3=D0=C1=BD=B8=F6=D2=D4=C9=CF=B5=C4=C0=E9=B0=CA=A1=A3=BD=E1=B9=FB=C0=E9=
=B0=CA=D0=CE=B3=C9=C1=CB=D2=BB=D5=C5=CD=F8=B7=D6=B8=EE=C1=CB=B2=BC=C0=CA=B5=
=C4=C4=C1=B3=A1=A1=A3=B2=BC=C0=CA=CF=EB=BD=AB=C4=C1=B3=A1=BB=D6=B8=B4=D4=AD=
=D1=F9=A3=AC=B3=F6=D3=DA=D5=E2=B8=F6=BF=BC=C2=C7=A3=AC=CB=FB=CA=D7=CF=C8=B5=
=C3=D6=AA=B5=C0=C4=C1=B3=A1=C9=CF=C4=C4=D2=BB=BF=E9=C7=F8=D3=F2=B5=C4=D6=DC=
=B3=A4=D7=EE=D0=A1=A1=A3<BR>=B2=BC=C0=CA=BD=AB=CB=FB=B5=C4=C3=BF=B6=CE=C0=
=E9=B0=CA=B4=D31=B5=BDN=BD=F8=D0=D0=C1=CB=B1=EA=BA=C5=A3=A8N=3D=CF=DF=B6=CE=
=B5=C4=D7=DC=CA=FD=A3=A9=A1=A3=CB=FB=D6=AA=B5=C0=C3=BF=B6=CE=C0=E9=B0=CA=B5=
=C4=D3=D0=C8=E7=CF=C2=CA=F4=D0=D4=A3=BA<BR><BR>=B8=C3=B6=CE=C0=E9=B0=CA=B5=
=C4=B3=A4=B6=C8=20
=
<BR>=B8=C3=B6=CE=C0=E9=B0=CA=B5=C4=D2=BB=B6=CB=CB=F9=C1=AC=BD=D3=B5=C4=C1=
=ED=D2=BB=B6=CE=C0=E9=B0=CA=B5=C4=B1=EA=BA=C5 =
<BR>=B8=C3=B6=CE=C0=E9=B0=CA=B5=C4=C1=ED=D2=BB=B6=CB=CB=F9=C1=AC=BD=D3=B5=
=C4=C1=ED=D2=BB=B6=CE=C0=E9=B0=CA=B5=C4=B1=EA=BA=C5=20
=
<BR>=D0=D2=D4=CB=B5=C4=CA=C7=A3=AC=C3=BB=D3=D0=C0=E9=B0=CA=C1=AC=BD=D3=CB=
=FC=D7=D4=C9=ED=A1=A3<BR>=B6=D4=D3=DA=D2=BB=D7=E9=D3=D0=B9=D8=C0=E9=B0=CA=
=C8=E7=BA=CE=B7=D6=B8=EE=C4=C1=B3=A1=B5=C4<SPAN class=3Dt_tag=20
=
href=3D"tag.php?name=3D%CA%FD%BE%DD">=CA=FD=BE=DD</SPAN>=A3=AC=D0=B4=D2=BB=
=B8=F6<SPAN class=3Dt_tag=20
=
href=3D"tag.php?name=3D%B3%CC%D0%F2">=B3=CC=D0=F2</SPAN>=C0=B4=BC=C6=CB=E3=
=B3=F6=CB=F9=D3=D0=B7=D6=B8=EE=B3=F6=B5=C4=C7=F8=D3=F2=D6=D0=D7=EE=D0=A1=B5=
=C4=D6=DC=B3=A4=A1=A3<BR>=C0=FD=C8=E7=A3=AC=B1=EA=BA=C51~10=B5=C4=C0=E9=B0=
=CA=D3=C9=CF=C2=CD=BC=B5=C4=D0=CE=CA=BD=D7=E9=B3=C9=A3=A8=CF=C2=C3=E6=B5=C4=
=CA=FD=D7=D6=CA=C7=C0=E9=B0=CA=B5=C4=B1=EA=BA=C5=A3=A9=A3=BA<BR>=A1=A1<BR=
><BR> =20
1<BR>+---------------+<BR>|\ =
=20
/|<BR> 2| \7 =20
/ |<BR>| \ =20
/ |<BR>+---+ / |6<BR>| 8 \=20
/10 |<BR> 3| =
=20
\9 / |<BR>| \ / =
=20
|<BR>+-------+-------+<BR> 4 =20
=
5<BR><BR>=C9=CF=CD=BC=D6=D0=D6=DC=B3=A4=D7=EE=D0=A1=B5=C4=C7=F8=D3=F2=CA=C7=
=D3=C92=A3=AC7=A3=AC8=BA=C5=C0=E9=B0=CA=D0=CE=B3=C9=B5=C4=A1=A3<BR>=A1=A1=
<BR><BR>PROGRAM NAME:=20
fence6<BR>INPUT FORMAT<BR>=B5=DA1=D0=D0: N (1 <=3D N <=3D =
100)=20
<BR>=B5=DA2=D0=D0=B5=BD=B5=DA3*N+1=D0=D0: =
=C3=BF=C8=FD=D0=D0=CE=AA=D2=BB=D7=E9=A3=AC=B9=B2N=D7=E9=D0=C5=CF=A2:<BR>=C3=
=BF=D7=E9=D0=C5=CF=A2=B5=C4=B5=DA1=D0=D0=D3=D04=B8=F6=D5=FB=CA=FD: s, =
=D5=E2=B6=CE=C0=E9=B0=CA=B5=C4=B1=EA=BA=C5(1=20
<=3D s <=3D N); Ls, =
the=D5=E2=B6=CE=C0=E9=B0=CA=B5=C4=B3=A4=B6=C8 (1 <=3D Ls <=3D =
255); N1s (1 <=3D N1s=20
<=3D 8) =
=D3=EB=B1=BE=B6=CE=C0=E9=B0=CA=B5=C4=D2=BB=B6=CB=CB=F9=CF=E0=C1=DA=B5=C4=C0=
=E9=B0=CA=B5=C4=CA=FD=C1=BF; and =
N2s=D3=EB=B1=BE=B6=CE=C0=E9=B0=CA=B5=C4=C1=ED=D2=BB=B6=CB=CB=F9=CF=E0=C1=DA=
=B5=C4=C0=E9=B0=CA=B5=C4=CA=FD=C1=BF=A1=A3 (1 <=3D N2s <=3D=20
=
8). <BR>=C3=BF=D7=E9=D0=C5=CF=A2=B5=C4=B5=C4=B5=DA2=D0=D0=D3=D0=
N1s=B8=F6=D5=FB=CA=FD, =
=B7=D6=B1=F0=C3=E8=CA=F6=D3=EB=B1=BE=B6=CE=C0=E9=B0=CA=B5=C4=D2=BB=B6=CB=CB=
=F9=CF=E0=C1=DA=B5=C4=C0=E9=B0=CA=B5=C4=B1=EA=BA=C5=A1=A3=20
=
<BR>=C3=BF=D7=E9=D0=C5=CF=A2=B5=C4=B5=C4=B5=DA3=D0=D0=D3=D0N2s=B8=F6=D5=FB=
=CA=FD, =
=B7=D6=B1=F0=C3=E8=CA=F6=D3=EB=B1=BE=B6=CE=C0=E9=B0=CA=B5=C4=C1=ED=D2=BB=B6=
=CB=CB=F9=CF=E0=C1=DA=B5=C4=C0=E9=B0=CA=B5=C4=B1=EA=BA=C5=A1=A3 =
<BR><BR><BR>SAMPLE INPUT=20
(file fence6.in) <BR><BR>10<BR>1 16 2 2<BR>2 7<BR>10 6<BR>2 3 2 =
2<BR>1=20
7<BR>8 3<BR>3 3 2 1<BR>8 2<BR>4<BR>4 8 1 3<BR>3<BR>9 10 5<BR>5 8 3 =
1<BR>9=20
10 4<BR>6<BR>6 6 1 2 <BR>5 <BR>1 10<BR>7 5 2 2 <BR>1 2<BR>8 9<BR>8 =
4 2=20
2<BR>2 3<BR>7 9<BR>9 5 2 3<BR>7 8<BR>4 5 10<BR>10 10 2 3<BR>1 =
6<BR>4 9=20
5<BR><BR>OUTPUT =
FORMAT<BR><BR>=CA=E4=B3=F6=B5=C4=C4=DA=C8=DD=CE=AA=B5=A5=B6=C0=B5=C4=D2=BB=
=D0=D0=A3=AC=D3=C3=D2=BB=B8=F6=D5=FB=CA=FD=C0=B4=B1=ED=CA=BE=D7=EE=D0=A1=B5=
=C4=D6=DC=B3=A4=A1=A3<BR><BR>SAMPLE=20
OUTPUT (file fence6.out)<BR><BR>12</DIV>
<P></P>
<HR>
<P></P>
<P><STRONG>USACO 4.1.3 Fence =
Loops<BR>=CC=E1=BD=BB=B4=CE=CA=FD:2=B4=CE</STRONG></P>
=
<P><STRONG>=B5=DA=D2=BB=B4=CE=CC=E1=BD=BB=CD=FC=C1=CB=BF=C9=C4=DC=D4=DAdf=
s=B9=FD=B3=CC=D3=F6=B5=BD=BB=B7=D5=D2=B3=C9=CB=C0=D1=AD=BB=B7=B5=C4=CE=CA=
=CC=E2.<BR>=D7=F6=C1=CB=D5=E2=B5=C0=CC=E2,=BA=DC=D3=D0=B8=D0=B4=A5,=D2=D4=
=C7=B0=C5=F6=B5=BD=D5=E2=B5=C0=CC=E2,=CF=EB=C6=C6=C4=D4=B4=FC=D2=B2=B2=BB=
=BB=E1=D7=F6,=CF=D6=D4=DA=D6=D8=CD=B7=D7=F6=D2=BB=B4=CEusaco,=D4=D9=D7=F6=
=B5=BD=D5=E2=CC=E2,=B7=A2=BE=F5=C6=E4=CA=B5=BA=DC=BC=F2=B5=A5.</STRONG></=
P>
=
<P><STRONG>=D5=E2=B5=C0=CC=E2=B8=F8=B5=C4=CA=FD=BE=DD=CA=C7=B1=DF=D6=AE=BC=
=E4=B5=C4=B9=D8=CF=B5,=D2=D4=C7=B0=CE=D2=CF=EB=B5=BD=B5=C4=CA=C7=B9=B9=CD=
=BC,=C8=BB=BA=F3=CC=D7=BE=AD=B5=E4=B5=C4=D7=EE=B6=CC=C2=B7=D7=F6.=B5=AB=CA=
=C7=D5=E2=B5=C0=CC=E2=B5=C4=CA=FD=BE=DD=CA=E4=C8=EB=BB=E1=CA=B9=B0=B4=B5=E3=
=B9=B9=CD=BC=BA=DC=C2=E9=B7=B3,=C6=E4=CA=B5=D5=E2=B5=C0=CC=E2=CB=D1=CB=F7=
=BC=B4=BF=C9,=B6=F8=C7=D2=BC=D3=BC=F4=D6=A6=BA=F3=BA=DC=BF=EC.=D3=C9v=CC=F5=
=B1=DF=BF=AA=CA=BC=CB=D1=CB=F7=D4=DA=CB=FCb=B7=BD=CF=F2=B5=C4=B1=DF,=D6=D8=
=B8=B4=D5=E2=B8=F6=B9=FD=B3=CC,=D6=B1=B5=BD=BB=D8=B5=BDv=B6=F8=C7=D2=CA=C7=
=D3=C9a=B7=BD=CF=F2=BB=D8=B5=BD=B5=C4,=CE=AA=C1=CB=C5=D0=B6=CF=BB=B7=BF=C9=
=D2=D4=BC=D3=B8=F6=C5=D0=D6=D8,=D2=BB=B8=F6=BC=F4=D6=A6:=B6=D4=D3=DA=C2=B7=
=BE=B6=B3=A4=B6=C8=B4=F3=D3=DA=D2=D1=D6=AA=D7=EE=D0=A1=BB=B7=B5=C4=BF=C9=BC=
=F4.</STRONG></P>
<P><STRONG>{<BR>TASK:fence6<BR>LANG:PASCAL<BR>}<BR>program=20
fence6;<BR>const<BR> =
maxq=3D10000;<BR> =20
maxn=3D100;<BR>var<BR> =
contact:array[1..maxn,1..2,0..8] of=20
integer;<BR> onleft:array[1..maxn,1..maxn] of=20
boolean;<BR> edge:array[1..maxn] of=20
integer;<BR> visit:array[1..maxn] of=20
boolean;<BR> n,min:integer;<BR>procedure=20
init;<BR>var<BR> =20
i,j,x,len,l,r:integer;<BR>begin<BR> =20
assign(input,'fence6.in');reset(input);<BR> =20
readln(n);<BR> =20
fillchar(onleft,sizeof(onleft),0);<BR> for =
i:=3D1 to n=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
readln(x,len,contact[x,1,0],contact[x,2,0]);<BR> &=
nbsp; =20
=
edge[x]:=3Dlen;<BR> =
=20
for j:=3D1 to contact[x,1,0]=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p; =20
=
read(contact[x,1,j]);<BR> =
=20
=
onleft[x,contact[x,1,j]]:=3Dtrue;<BR> =
=20
=
end;<BR>  =
;=20
=
readln;<BR> &n=
bsp;=20
for j:=3D1 to contact[x,2,0]=20
=
do<BR> &=
nbsp; =20
=
read(contact[x,2,j]);<BR> =
=20
readln;<BR> =20
end;<BR> close(input);<BR>end;<BR>procedure=20
dfs(start,v,gfr,dis:integer);<BR>var<BR> =20
i,gto,sfr,now:integer;<BR>begin<BR> if =
dis>min then=20
exit;<BR> if gfr=3D1 then gto:=3D2 else=20
gto:=3D1;<BR> for i:=3D1 to contact[v,gto,0]=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
now:=3Dcontact[v,gto,i];<BR> &nb=
sp; =20
if onleft[now,v] then sfr:=3D1 else=20
=
sfr:=3D2;<BR> =
=20
if (now=3Dstart)and(sfr=3D1)=20
=
then<BR>  =
; =20
if dis<min=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p;  =
;=20
=
min:=3Ddis;<BR> &nbs=
p;  =
; =20
=
exit;<BR> &nbs=
p; =20
=
end;<BR>  =
;=20
if not visit[now]=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
visit[now]:=3Dtrue;<BR> &n=
bsp; =20
=
dfs(start,now,sfr,dis+edge[now]);<BR> =
&=
nbsp;=20
=
visit[now]:=3Dfalse;<BR> &=
nbsp; =20
end;<BR> =20
end;<BR>end;<BR>procedure work;<BR>var<BR> =20
i,len:integer;<BR>begin<BR> =20
min:=3Dmaxint;<BR> for i:=3D1 to n=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
fillchar(visit,sizeof(visit),0);<BR> &=
nbsp; =20
dfs(i,i,1,edge[i]);<BR> =20
end;<BR> =20
assign(output,'fence6.out');rewrite(output);<BR> =
writeln(min);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.</STRONG></P><STRONG>
<HR>
</STRONG>
<P><STRONG>USACO=B5=C4=CC=E2=BD=E2</STRONG></P>
<P><STRONG>The first problem is to switch the problem into a =
graph. The=20
easiest graph representation to use is an adjacency list, where =
each node=20
has the list of edges which are incident to it. The problem =
specifies that=20
the endpoint of each edge will coincide with no more than 8 other=20
endpoints. </STRONG></P>
<P><STRONG>For simplicity, let the endpoints of fence segments be =
the=20
nodes of the graph, and the edges be of two types: the ones across =
fence=20
segments and the ones connecting points which are at the same =
location=20
(another alternative is to just have one node for each location).=20
</STRONG></P>
<P><STRONG>Given the input, it's fairly simple to determine which =
side of=20
fence A that fence B is connected to by determining which adjaency =
list of=20
fence B contains A. </STRONG></P>
<P><STRONG>Once the graph representation is done, the problem is =
to find=20
the shortest cycle (edges between nodes at the same location are=20
considered to have length zero). For each edge, find the minimum =
length=20
simple cycle which contains it by deleting that edge and finding =
the=20
minimum length path from one end of the edge to the other. We can =
just use=20
Dijkstra's to determine the shortest path. =
</STRONG></P><PRE><STRONG>#include <stdio.h>
/* maximum number of segments */
#define MAXS 100
/* an edge is a fence segment */
/* a place is a side of a fence segment */
/* there are two places for each edge */
/* conn is the index of the incident edge */
/* alist is the index of the incident place */
int conn[2*MAXS][8]; /* one edge list for each side of each segment */
int ccnt[2*MAXS]; /* number of incident edges */
int length[MAXS]; /* length of the segments */
int alist[2*MAXS][8]; /* adjacency list for each end of each segment */
int nfence; /* numbor of fences */
int npl; /* number of places */
int dist[2*MAXS]; /* distance to each place */
/* heap data structure */
int heap[2*MAXS];=20
int hsize;
int hloc[2*MAXS]; /* location within heap of each place */
/* debugging routine */
/* ensure heap order has been maintained */
void check_heap(void)
{
int lv;
for (lv =3D 1; lv < hsize; lv++)
{
if (dist[heap[lv]] < dist[heap[(lv-1)/2]])
{
fprintf (stderr, "HEAP ERROR!\n");
return;
}
}
}
/* delete the minimum item from the heap */
void delete_min(void)
{
int loc, val;
int p, t;
/* remove last item in the heap array */
loc =3D heap[--hsize];
val =3D dist[loc];
p =3D 0;
while (2*p+1 < hsize)
{
/* find smaller child */
t =3D 2*p+1;
if (t+1 < hsize && dist[heap[t+1]] < dist[heap[t]]) =
t++;
/* if child less than the removed item, move child up */
if (dist[heap[t]] < val)
{
heap[p] =3D heap[t];
hloc[heap[p]] =3D p;
p =3D t;
} else break; /* otherwise, put removed item here */
}
/* put removed item back into the heap */
heap[p] =3D loc;
hloc[loc] =3D p;
check_heap(); /* sanity check */
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -