📄 usaco 3_3_1 riding the fences 题解_leokan的blog.mht
字号:
<DIV class=3Dstagepad>
<DIV style=3D"WIDTH: 100%">
<TABLE class=3Dmodth cellSpacing=3D0 cellPadding=3D0 width=3D"100%" =
border=3D0>
<TBODY>
<TR>
<TD class=3Dmodtl width=3D7> </TD>
<TD class=3Dmodtc noWrap>
<DIV class=3Dmodhead><SPAN =
class=3Dmodtit>=B2=E9=BF=B4=CE=C4=D5=C2</SPAN></DIV></TD>
<TD class=3Dmodtc noWrap align=3Dright></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 3.3.1 Riding the Fences =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA02=D4=C208=C8=D5 =D0=C7=C6=DA=CE=E5 =
12:17</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<P></P>
<H2>USACO 3.3.1 Riding the Fences</H2>
<DIV class=3Dt_msgfont>Riding the Fences<BR><BR>Farmer John owns a =
large=20
number of fences that must be repaired annually. He traverses the =
fences=20
by riding a horse along each and every one of them (and nowhere =
else) and=20
fixing the broken parts. <BR><BR>Farmer John is as lazy as the =
next farmer=20
and hates to ride the same fence twice. Your program must read in =
a=20
description of a network of fences and tell Farmer John a path to =
traverse=20
each fence length exactly once, if possible. Farmer J can, if he =
wishes,=20
start and finish at any fence intersection. <BR><BR>Every fence =
connects=20
two fence intersections, which are numbered inclusively from 1 =
through 500=20
(though some farms have far fewer than 500 intersections). Any =
number of=20
fences (>=3D1) can meet at a fence intersection. It is always =
possible to=20
ride from any fence to any other fence (i.e., all fences are =
"connected").=20
<BR><BR>Your program must output the path of intersections that, =
if=20
interpreted as a base 500 number, would have the smallest =
magnitude.=20
<BR><BR>There will always be at least one solution for each set of =
input=20
data supplied to your program for testing. <BR><BR>PROGRAM NAME:=20
fence<BR>INPUT FORMAT<BR>Line 1: The number of fences, =
F (1=20
<=3D F <=3D 1024) <BR>Line 2..F+1: A =
pair of=20
integers (1 <=3D i,j <=3D 500) that tell which pair of =
intersections=20
this fence connects. <BR><BR>SAMPLE INPUT (file =
fence.in)=20
<BR>9<BR>1 2<BR>2 3<BR>3 4<BR>4 2<BR>4 5<BR>2 5<BR>5 6<BR>5 7<BR>4 =
6<BR><BR>OUTPUT FORMAT<BR>The output consists of F+1 lines, each=20
containing a single integer. Print the number of the starting =
intersection=20
on the first line, the next intersection's number on the next =
line, and so=20
on, until the final intersection on the last line. There might be =
many=20
possible answers to any given input set, but only one is ordered=20
correctly. <BR><BR>SAMPLE OUTPUT (file=20
=
fence.out)<BR>1<BR>2<BR>3<BR>4<BR>2<BR>5<BR>4<BR>6<BR>5<BR>7<BR><BR><BR><=
BR>Riding=20
the Fences<BR><BR>=C6=EF=C2=ED=D0=DE=D5=A4=C0=B8<BR><BR>=D2=EB by=20
=
Jeru<BR>=A1=A1<BR><BR><BR>=A1=A1=A1=A1=C5=A9=C3=F1John=C3=BF=C4=EA=D3=D0=BA=
=DC=B6=E0=D5=A4=C0=B8=D2=AA=D0=DE=C0=ED=A1=A3=CB=FB=D7=DC=CA=C7=C6=EF=D7=C5=
=C2=ED=B4=A9=B9=FD=C3=BF=D2=BB=B8=F6=D5=A4=C0=B8=B2=A2=D0=DE=B8=B4=CB=FC=C6=
=C6=CB=F0=B5=C4=B5=D8=B7=BD=A1=A3=20
=
<BR><BR>=A1=A1=A1=A1John=CA=C7=D2=BB=B8=F6=D3=EB=C6=E4=CB=FB=C5=A9=C3=F1=D2=
=BB=D1=F9=C0=C1=B5=C4=C8=CB=A1=A3=CB=FB=CC=D6=D1=E1=C6=EF=C2=ED=A3=AC=D2=F2=
=B4=CB=B4=D3=C0=B4=B2=BB=C1=BD=B4=CE=BE=AD=B9=FD=D2=BB=B8=F6=D2=BB=B8=F6=D5=
=A4=C0=B8=A1=A3=C4=E3=B1=D8=D0=EB=B1=E0=D2=BB=B8=F6=B3=CC=D0=F2=A3=AC=B6=C1=
=C8=EB=D5=A4=C0=B8=CD=F8=C2=E7=B5=C4=C3=E8=CA=F6=A3=AC=B2=A2=BC=C6=CB=E3=B3=
=F6=D2=BB=CC=F5=D0=DE=D5=A4=C0=B8=B5=C4=C2=B7=BE=B6=A3=AC=CA=B9=C3=BF=B8=F6=
=D5=A4=C0=B8=B6=BC=C7=A1=BA=C3=B1=BB=BE=AD=B9=FD=D2=BB=B4=CE=A1=A3John=C4=
=DC=B4=D3=C8=CE=BA=CE=D2=BB=B8=F6=B6=A5=B5=E3(=BC=B4=C1=BD=B8=F6=D5=A4=C0=
=B8=B5=C4=BD=BB=B5=E3)=BF=AA=CA=BC=C6=EF=C2=ED=A3=AC=D4=DA=C8=CE=D2=E2=D2=
=BB=B8=F6=B6=A5=B5=E3=BD=E1=CA=F8=A1=A3=20
=
<BR><BR>=A1=A1=A1=A1=C3=BF=D2=BB=B8=F6=D5=A4=C0=B8=C1=AC=BD=D3=C1=BD=B8=F6=
=B6=A5=B5=E3=A3=AC=B6=A5=B5=E3=D3=C31=B5=BD500=B1=EA=BA=C5(=CB=E4=C8=BB=D3=
=D0=B5=C4=C5=A9=B3=A1=B2=A2=C3=BB=D3=D0500=B8=F6=B6=A5=B5=E3)=A1=A3=D2=BB=
=B8=F6=B6=A5=B5=E3=C9=CF=BF=C9=C1=AC=BD=D3=C8=CE=D2=E2=B6=E0(>=3D1)=B8=
=F6=D5=A4=C0=B8=A1=A3=CB=F9=D3=D0=D5=A4=C0=B8=B6=BC=CA=C7=C1=AC=CD=A8=B5=C4=
(=D2=B2=BE=CD=CA=C7=C4=E3=BF=C9=D2=D4=B4=D3=C8=CE=D2=E2=D2=BB=B8=F6=D5=A4=
=C0=B8=B5=BD=B4=EF=C1=ED=CD=E2=B5=C4=CB=F9=D3=D0=D5=A4=C0=B8)=A1=A3=20
=
<BR><BR>=A1=A1=A1=A1=C4=E3=B5=C4=B3=CC=D0=F2=B1=D8=D0=EB=CA=E4=B3=F6=C6=EF=
=C2=ED=B5=C4=C2=B7=BE=B6(=D3=C3=C2=B7=C9=CF=D2=C0=B4=CE=BE=AD=B9=FD=B5=C4=
=B6=A5=B5=E3=BA=C5=C2=EB=B1=ED=CA=BE)=A1=A3=CE=D2=C3=C7=C8=E7=B9=FB=B0=D1=
=CA=E4=B3=F6=B5=C4=C2=B7=BE=B6=BF=B4=B3=C9=CA=C7=D2=BB=B8=F6500=BD=F8=D6=C6=
=B5=C4=CA=FD=A3=AC=C4=C7=C3=B4=B5=B1=B4=E6=D4=DA=B6=E0=D7=E9=BD=E2=B5=C4=C7=
=E9=BF=F6=CF=C2=A3=AC=CA=E4=B3=F6500=BD=F8=D6=C6=B1=ED=CA=BE=B7=A8=D6=D0=D7=
=EE=D0=A1=B5=C4=D2=BB=B8=F6=20
=
(=D2=B2=BE=CD=CA=C7=CA=E4=B3=F6=B5=DA=D2=BB=B8=F6=CA=FD=BD=CF=D0=A1=B5=C4=
=A3=AC=C8=E7=B9=FB=BB=B9=D3=D0=B6=E0=D7=E9=BD=E2=A3=AC=CA=E4=B3=F6=B5=DA=B6=
=FE=B8=F6=CA=FD=BD=CF=D0=A1=B5=C4=A3=AC=B5=C8=B5=C8)=A1=A3 =
<BR><BR>=A1=A1=A1=A1=CA=E4=C8=EB<SPAN class=3Dt_tag=20
=
href=3D"tag.php?name=3D%CA%FD%BE%DD">=CA=FD=BE=DD</SPAN>=B1=A3=D6=A4=D6=C1=
=C9=D9=D3=D0=D2=BB=B8=F6=BD=E2=A1=A3 <BR><BR>PROGRAM NAME:=20
fence<BR><BR>INPUT FORMAT<BR><BR>=B5=DA1=D0=D0: =
=D2=BB=B8=F6=D5=FB=CA=FDF(1 <=3D F <=3D=20
=
1024)=A3=AC=B1=ED=CA=BE=D5=A4=C0=B8=B5=C4=CA=FD=C4=BF <BR>=B5=DA=
2=B5=BDF+1=D0=D0: =C3=BF=D0=D0=C1=BD=B8=F6=D5=FB=CA=FDi, j(1 <=3D i,j =
<=3D=20
=
500)=B1=ED=CA=BE=D5=E2=CC=F5=D5=A4=C0=B8=C1=AC=BD=D3i=D3=EBj=BA=C5=B6=A5=B5=
=E3=A1=A3 <BR><BR>SAMPLE INPUT(fence.in) <BR>9<BR>1=20
2<BR>2 3<BR>3 4<BR>4 2<BR>4 5<BR>2 5<BR>5 6<BR>5 7<BR>4 =
6<BR><BR>OUTPUT=20
=
FORMAT<BR>=A1=A1=A1=A1=CA=E4=B3=F6=D3=A6=B5=B1=D3=D0F+1=D0=D0=A3=AC=C3=BF=
=D0=D0=D2=BB=B8=F6=D5=FB=CA=FD=A3=AC=D2=C0=B4=CE=B1=ED=CA=BE=C2=B7=BE=B6=BE=
=AD=B9=FD=B5=C4=B6=A5=B5=E3=BA=C5=A1=A3=D7=A2=D2=E2=CA=FD=BE=DD=BF=C9=C4=DC=
=D3=D0=B6=E0=D7=E9=BD=E2=A3=AC=B5=AB=CA=C7=D6=BB=D3=D0=C9=CF=C3=E6<SPAN=20
class=3Dt_tag =
href=3D"tag.php?name=3D%CC%E2%C4%BF">=CC=E2=C4=BF</SPAN>=D2=AA=C7=F3=B5=C4=
=C4=C7=D2=BB=D7=E9=BD=E2=CA=C7=C8=CF=CE=AA=D5=FD=C8=B7=B5=C4=A1=A3=20
<BR><BR>SAMPLE=20
=
OUTPUT(fence.out)<BR>1<BR>2<BR>3<BR>4<BR>2<BR>5<BR>4<BR>6<BR>5<BR>7</DIV>=
<P></P>
<HR>
<P></P>
<P></P>
<P><STRONG>USACO 3.3.1 Riding the =
Fences<BR>=CC=E1=BD=BB=B4=CE=CA=FD:2=B4=CE</STRONG></P>
=
<P><STRONG>=B4=F2=B4=ED=C1=CB=B8=F6=B1=E4=C1=BF=C3=FB...=CC=E1=BD=BB=B6=E0=
=C1=CB=D2=BB=B4=CE.<BR>=D4=AD=CF=C8=CA=C7=D3=C3=C1=DA=BD=D3=BE=D8=D5=F3=D7=
=F6=B5=C4,=D5=E2=B4=CE=BB=B9=CA=C7=D3=C3=C1=DA=BD=D3=BE=D8=D5=F3=D7=F6,=B2=
=BB=B9=FD=BF=AA=B6=E0=D2=BB=B8=F6=CA=FD=D7=E9=BC=C7=C2=BC=D2=BB=B8=F6=B5=E3=
=C1=AC=BD=D3=D7=C5=C4=C4=BC=B8=B8=F6=B5=E3,=D5=E2=D1=F9=B2=BB=D3=C3=C3=A4=
=C4=BF=C3=B6=BE=D9,=BF=C9=D2=D4=BF=EC=D2=BB=D0=A9.=20
</STRONG></P>
<P><STRONG>{<BR>TASK:fence<BR>LANG:PASCAL<BR>}<BR>program=20
fence;<BR>const<BR> =20
maxn=3D500;<BR>var<BR> ans:array[0..maxn*10] of=20
integer;<BR> map:array[1..maxn,1..maxn] of=20
integer;<BR> connect:array[1..maxn,0..maxn*10] =
of=20
integer;<BR> n:integer;<BR>procedure swap(var=20
x,y:integer);<BR>var<BR> =20
t:integer;<BR>begin<BR> =
t:=3Dx;<BR> =20
x:=3Dy;<BR> y:=3Dt;<BR>end;<BR>procedure=20
qs(f,l,arr:integer);<BR>var<BR> =20
i,j:integer;<BR> =20
x:integer;<BR>begin<BR> =
i:=3Df;<BR> =20
j:=3Dl;<BR> x:=3Dconnect[arr,(i+j)shr=20
1];<BR> =20
repeat<BR> =20
=
begin<BR> &nbs=
p;=20
while connect[arr,j]>x do=20
=
dec(j);<BR> &n=
bsp;=20
while connect[arr,i]<x do=20
=
inc(i);<BR> &n=
bsp;=20
if i<=3Dj=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
swap(connect[arr,i],connect[arr,j]);<BR> &nb=
sp; &nbs=
p; =20
=
inc(i);<BR> &n=
bsp; =20
=
dec(j);<BR> &n=
bsp; =20
end;<BR> =20
end;<BR> until i>j;<BR> if =
i<l=20
then qs(i,l,arr);<BR> if j>f then=20
qs(f,j,arr);<BR>end;<BR>procedure =
init;<BR>var<BR> =20
i,y,x,j:integer;<BR> =20
noon:boolean;<BR>begin<BR> =20
assign(input,'fence.in');reset(input);<BR> =20
fillchar(map,sizeof(map),0);<BR> =20
fillchar(connect,sizeof(connect),0);<BR> =20
readln(n);<BR> for i:=3D1 to n=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
readln(x,y);<BR> &nb=
sp; =20
=
inc(map[x,y]);<BR> &=
nbsp; =20
=
inc(map[y,x]);<BR> &=
nbsp; =20
=
inc(connect[x,0]);<BR> &nb=
sp; =20
=
connect[x,connect[x,0]]:=3Dy;<BR> &nbs=
p; =20
=
inc(connect[y,0]);<BR> &nb=
sp; =20
=
connect[y,connect[y,0]]:=3Dx;<BR> &nbs=
p;=20
end;<BR> for i:=3D1 to 500=20
do<BR> if =
connect[i,0]>0=20
=
then<BR>  =
;=20
qs(1,connect[i,0],i);<BR> =20
fillchar(ans,sizeof(ans),0);<BR> =20
close(input);<BR>end;<BR>procedure=20
dfs(v0:integer);<BR>var<BR> =20
i:integer;<BR>begin<BR> for i:=3D1 to =
connect[v0,0]=20
do<BR> if=20
map[v0,connect[v0,i]]>0=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
dec(map[v0,connect[v0,i]]);<BR> =
=20
=
dec(map[connect[v0,i],v0]);<BR> =
=20
=
dfs(connect[v0,i]);<BR> &n=
bsp; =20
end;<BR> inc(ans[0]);<BR> =20
ans[ans[0]]:=3Dv0;<BR>end;<BR>procedure =
work;<BR>var<BR> =20
i:integer;<BR>begin<BR> =20
assign(output,'fence.out');rewrite(output);<BR> =
for i:=3D1=20
to 500 do<BR> if=20
odd(connect[i,0]) then break;<BR> if =
(i=3D500)and not=20
odd(connect[i,0]) then dfs(1)<BR> else=20
dfs(i);<BR> for i:=3Dans[0] downto 1=20
do<BR> =20
writeln(ans[i]);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.</STRONG></P><STRONG>
<HR>
</STRONG>
<P><STRONG>USACO=B7=D6=CE=F6</STRONG></P>
<P><STRONG>Assuming you pick the lowest index vertex connected to =
each=20
node, the Eulerian Path algorithm actually determines the path =
requested,=20
although in the reverse direction. You must start the path =
determination=20
at the lowest legal vertex for this to =
work.</STRONG></P><PRE><STRONG>/* Prob #5: Riding the Fences */
#include <stdio.h>
#include <string.h>
#define MAXI 500
#define MAXF 1200
char conn[MAXI][MAXI];
int deg[MAXI];
int nconn;
int touched[MAXI];
int path[MAXF];
int plen;
/* Sanity check routine */
void fill(int loc)
{
int lv;
touched[loc] =3D 1;
for (lv =3D 0; lv < nconn; lv++)
if (conn[loc][lv] && !touched[lv])
fill(lv);
}
/* Sanity check routine */
int is_connected(int st)
{
int lv;
memset(touched, 0, sizeof(touched));
fill(st);
for (lv =3D 0; lv < nconn; lv++)
if (deg[lv] && !touched[lv])
return 0;
return 1;
}
/* this is exactly the Eulerian Path algorithm */
void find_path(int loc)
{
int lv;
for (lv =3D 0; lv < nconn; lv++)
if (conn[loc][lv])
{
/* delete edge */
conn[loc][lv]--;
conn[lv][loc]--;
deg[lv]--;
deg[loc]--;
/* find path from new location */
find_path(lv);
}
/* add this node to the `end' of the path */
path[plen++] =3D loc;
}
int main(int argc, char **argv)
{
FILE *fin, *fout;
int nfen;
int lv;
int x, y;
if (argc =3D=3D 1)=20
{
if ((fin =3D fopen("fence.in", "r")) =3D=3D NULL)
{
perror ("fopen fin");
exit(1);
}
if ((fout =3D fopen("fence.out", "w")) =3D=3D NULL)
{
perror ("fopen fout");
exit(1);
}
} else {
if ((fin =3D fopen(argv[1], "r")) =3D=3D NULL)
{
perror ("fopen fin filename");
exit(1);
}
fout =3D stdout;
}
fscanf (fin, "%d", &nfen);
for (lv =3D 0; lv < nfen; lv++)
{
fscanf (fin, "%d %d", &x, &y);
x--; y--;
conn[x][y]++;
conn[y][x]++;
deg[x]++;
deg[y]++;
if (x >=3D nconn) nconn =3D x+1;
if (y >=3D nconn) nconn =3D y+1;
}
/* find first node of odd degree */
for (lv =3D 0; lv < nconn; lv++)
if (deg[lv] % 2 =3D=3D 1) break;
/* if no odd-degree node, find first node with non-zero degree */
if (lv >=3D nconn)
for (lv =3D 0; lv < nconn; lv++)
if (deg[lv]) break;
#ifdef CHECKSANE
if (!is_connected(lv)) /* input sanity check */
{
fprintf (stderr, "Not connected?!?\n");
return 0;
}
#endif
/* find the eulerian path */
find_path(lv);=20
/* the path is discovered in reverse order */
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -