📄 usaco 4_2_2 the perfect stall 题解_leokan的blog.mht
字号:
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 4.2.2 The Perfect Stall =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA02=D4=C221=C8=D5 =D0=C7=C6=DA=CB=C4 =
23:22</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 4.2.2 The Perfect Stall</H2>
<DIV class=3Dt_msgfont>The Perfect Stall<BR>Hal Burch <BR>Farmer =
John=20
completed his new barn just last week, complete with all the =
latest=20
milking technology. Unfortunately, due to engineering problems, =
all the=20
stalls in the new barn are different. For the first week, Farmer =
John=20
randomly assigned cows to stalls, but it quickly became clear that =
any=20
given cow was only willing to produce milk in certain stalls. For =
the last=20
week, Farmer John has been collecting data on which cows are =
willing to=20
produce milk in which stalls. A stall may be only assigned to one =
cow,=20
and, of course, a cow may be only assigned to one stall. =
<BR><BR>Given the=20
preferences of the cows, compute the maximum number of =
milk-producing=20
assignments of cows to stalls that is possible. <BR><BR>PROGRAM =
NAME:=20
stall4<BR>INPUT FORMAT<BR>Line 1: One line with two =
integers,=20
N (0 <=3D N <=3D 200) and M (0 <=3D M <=3D 200). N is =
the number of=20
cows that Farmer John has and M is the number of stalls in the new =
barn. <BR>Line 2..N+1: N lines, each =
corresponding=20
to a single cow. The first integer (Si) on the line is the number =
of=20
stalls that the cow is willing to produce milk in (0 <=3D Si =
<=3D M).=20
The subsequent Si integers on that line are the stalls in which =
that cow=20
is willing to produce milk. The stall numbers will be integers in =
the=20
range (1..M), and no stall will be listed twice for a given=20
cow. <BR><BR>SAMPLE INPUT (file stall4.in) <BR>5 5<BR>2 =
2=20
5<BR>3 2 3 4<BR>2 1 5<BR>3 1 2 5<BR>1 2 <BR><BR>OUTPUT FORMAT<BR>A =
single=20
line with a single integer, the maximum number of milk-producing =
stall=20
assignments that can be made. <BR><BR>SAMPLE OUTPUT (file=20
stall4.out)<BR>4<BR><BR><BR><BR>The Perfect Stall =
<BR>=CD=EA=C3=C0=B5=C4=C5=A3=C0=B8<BR><BR>Hal=20
Burch<BR><BR>=D2=EB by Felicia=20
=
Crazy<BR><BR>=C5=A9=B7=F2=D4=BC=BA=B2=C9=CF=B8=F6=D0=C7=C6=DA=B8=D5=B8=D5=
=BD=A8=BA=C3=C1=CB=CB=FB=B5=C4=D0=C2=C5=A3=C5=EF=A3=AC=CB=FB=CA=B9=D3=C3=C1=
=CB=D7=EE=D0=C2=B5=C4=BC=B7=C4=CC=BC=BC=CA=F5=A1=A3=B2=BB=D0=D2=B5=C4=CA=C7=
=A3=AC=D3=C9=D3=DA=B9=A4=B3=CC=CE=CA=CC=E2=A3=AC=C3=BF=B8=F6=C5=A3=C0=B8=B6=
=BC=B2=BB=D2=BB=D1=F9=A1=A3=B5=DA=D2=BB=B8=F6=D0=C7=C6=DA=A3=AC=C5=A9=B7=F2=
=D4=BC=BA=B2=CB=E6=B1=E3=B5=D8=C8=C3=C4=CC=C5=A3=C3=C7=BD=F8=C8=EB=C5=A3=C0=
=B8=A3=AC=B5=AB=CA=C7=CE=CA=CC=E2=BA=DC=BF=EC=B5=D8=CF=D4=C2=B6=B3=F6=C0=B4=
=A3=BA=C3=BF=CD=B7=C4=CC=C5=A3=B6=BC=D6=BB=D4=B8=D2=E2=D4=DA=CB=FD=C3=C7=CF=
=B2=BB=B6=B5=C4=C4=C7=D0=A9=C5=A3=C0=B8=D6=D0=B2=FA=C4=CC=A1=A3=C9=CF=B8=F6=
=D0=C7=C6=DA=A3=AC=C5=A9=B7=F2=D4=BC=BA=B2=B8=D5=B8=D5=CA=D5=BC=AF=B5=BD=C1=
=CB=C4=CC=C5=A3=C3=C7=B5=C4=B0=AE=BA=C3=B5=C4=D0=C5=CF=A2=A3=A8=C3=BF=CD=B7=
=C4=CC=C5=A3=CF=B2=BB=B6=D4=DA=C4=C4=D0=A9=C5=A3=C0=B8=B2=FA=C4=CC=A3=A9=A1=
=A3=D2=BB=B8=F6=C5=A3=C0=B8=D6=BB=C4=DC=C8=DD=C4=C9=D2=BB=CD=B7=C4=CC=C5=A3=
=A3=AC=B5=B1=C8=BB=A3=AC=D2=BB=CD=B7=C4=CC=C5=A3=D6=BB=C4=DC=D4=DA=D2=BB=B8=
=F6=C5=A3=C0=B8=D6=D0=B2=FA=C4=CC=A1=A3<BR><BR>=B8=F8=B3=F6=C4=CC=C5=A3=C3=
=C7=B5=C4=B0=AE=BA=C3=B5=C4=D0=C5=CF=A2=A3=AC=BC=C6=CB=E3=D7=EE=B4=F3=B7=D6=
=C5=E4=B7=BD=B0=B8=A1=A3=20
<BR><BR>PROGRAM NAME: stall4<BR>INPUT =
FORMAT<BR>=B5=DA=D2=BB=D0=D0 =C1=BD=B8=F6=D5=FB=CA=FD=A3=ACN =
(0=20
<=3D N <=3D 200) =BA=CD M (0 <=3D M <=3D 200) =A1=A3N =
=CA=C7=C5=A9=B7=F2=D4=BC=BA=B2=B5=C4=C4=CC=C5=A3=CA=FD=C1=BF=A3=ACM =
=CA=C7=D0=C2=C5=A3=C5=EF=B5=C4=C5=A3=C0=B8=CA=FD=C1=BF=A1=A3=20
<BR>=B5=DA=B6=FE=D0=D0=B5=BD=B5=DAN+1=D0=D0 =
=D2=BB=B9=B2 N =
=D0=D0=A3=AC=C3=BF=D0=D0=B6=D4=D3=A6=D2=BB=D6=BB=C4=CC=C5=A3=A1=A3=B5=DA=D2=
=BB=B8=F6=CA=FD=D7=D6 (Si) =
=CA=C7=D5=E2=CD=B7=C4=CC=C5=A3=D4=B8=D2=E2=D4=DA=C6=E4=D6=D0=B2=FA=C4=CC=B5=
=C4=C5=A3=C0=B8=B5=C4=CA=FD=C4=BF (0=20
<=3D Si <=3D M) =A1=A3=BA=F3=C3=E6=B5=C4 Si =
=B8=F6=CA=FD=B1=ED=CA=BE=D5=E2=D0=A9=C5=A3=C0=B8=B5=C4=B1=E0=BA=C5=A1=A3=C5=
=A3=C0=B8=B5=C4=B1=E0=BA=C5=CF=DE=B6=A8=D4=DA=C7=F8=BC=E4 (1..M)=20
=
=D6=D0=A3=AC=D4=DA=CD=AC=D2=BB=D0=D0=A3=AC=D2=BB=B8=F6=C5=A3=C0=B8=B2=BB=BB=
=E1=B1=BB=C1=D0=B3=F6=C1=BD=B4=CE=A1=A3<BR><BR><BR>SAMPLE INPUT (file =
stall4.in)<BR>5 5<BR>2 2=20
5<BR>3 2 3 4<BR>2 1 5<BR>3 1 2 5<BR>1 2 <BR><BR>OUTPUT=20
=
FORMAT<BR>=D6=BB=D3=D0=D2=BB=D0=D0=A1=A3=CA=E4=B3=F6=D2=BB=B8=F6=D5=FB=CA=
=FD=A3=AC=B1=ED=CA=BE=D7=EE=B6=E0=C4=DC=B7=D6=C5=E4=B5=BD=B5=C4=C5=A3=C0=B8=
=B5=C4=CA=FD=C1=BF=A1=A3 <BR><BR>SAMPLE OUTPUT (file=20
stall4.out)<BR>4</DIV>
<HR>
<P><STRONG>USACO 4.2.2 The Perfect =
Stall<BR>=CC=E1=BD=BB=B4=CE=CA=FD:1=B4=CE</STRONG></P>
=
<P><STRONG>=D4=D9=C1=B7=CF=B0=D2=BB=B4=CE,=D5=E2=D6=D6=CC=E2=CE=D2=BE=F5=B5=
=C3=D3=C3=C1=DA=BD=D3=B1=ED=BF=C9=D2=D4=CA=A1=C8=A5=C3=B6=BE=D9=C4=C4=B8=F6=
=BD=E1=B5=E3=D3=D0=C1=AC=BD=D3=B5=C4=CA=B1=BC=E4.=B0=FC=C0=A8spfa,=D7=EE=B4=
=F3=C1=F7=D6=AE=C0=E0=B5=C4=CE=D2=D3=C3=C1=DA=BD=D3=BE=D8=D5=F3=C5=E4=BA=CF=
=C1=DA=BD=D3=B1=ED=B6=BC=B1=C8=B5=A5=B4=BF=C1=DA=BD=D3=BE=D8=D5=F3=BF=EC.=
=D6=C1=D3=DA=B1=DF=B1=ED...=BB=B9=B2=BB=BB=E1=D3=C3.</STRONG></P>
<P><STRONG>{<BR>TASK:stall4<BR>LANG:PASCAL<BR>}<BR>program=20
stall4;<BR>const<BR> =
maxn=3D200;<BR> =20
maxm=3D200;<BR>var<BR> =
contact:array[1..maxn,0..maxm] of=20
integer;<BR> visit:array[1..maxm] of=20
boolean;<BR> link:array[1..maxm] of=20
integer;<BR> n,m:integer;<BR>procedure=20
init;<BR>var<BR> =20
i,j:integer;<BR>begin<BR> =20
assign(input,'stall4.in');reset(input);<BR> =20
readln(n,m);<BR> =20
fillchar(contact,sizeof(contact),0);<BR> for =
i:=3D1 to n=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
read(contact[i,0]);<BR> &n=
bsp; =20
for j:=3D1 to contact[i,0]=20
=
do<BR> &=
nbsp; =20
=
read(contact[i,j]);<BR> &n=
bsp; =20
readln;<BR> =20
end;<BR> close(input);<BR>end;<BR>function=20
find(v:integer):boolean;<BR>var<BR> =20
i:integer;<BR>begin<BR> for i:=3D1 to =
contact[v,0]=20
do<BR> if not=20
visit[contact[v,i]]=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
visit[contact[v,i]]:=3Dtrue;<BR>  =
; =20
if (link[contact[v,i]]=3D0) or find(link[contact[v,i]])=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p;  =
;=20
=
link[contact[v,i]]:=3Dv;<BR> &nb=
sp; &nbs=
p; =20
=
exit(true);<BR> &nbs=
p; =20
=
end;<BR>  =
;=20
end;<BR> exit(false);<BR>end;<BR>procedure=20
work;<BR>var<BR> =20
i,max:integer;<BR>begin<BR> =20
fillchar(link,sizeof(link),0);<BR> =20
max:=3D0;<BR> for i:=3D1 to n=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
fillchar(visit,sizeof(visit),0);<BR> &=
nbsp; =20
if find(i) then =
inc(max);<BR> =20
end;<BR> =20
assign(output,'stall4.out');rewrite(output);<BR> =
writeln(max);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.</STRONG></P><STRONG>
<HR>
</STRONG>
<P><STRONG></STRONG></P>
<P><STRONG>This is a straight-forward maximum matching algorithm. =
The only=20
difference in the program below is that the graph is not stored =
directly.=20
Instead, the likes of each cows is maintained, along with the =
cow/stall=20
assignments. The graph can be determined quickly using only this=20
information. </STRONG></P><PRE><STRONG>#include <stdio.h>
#include <string.h>
/* maximum number of cows */
#define MAXC 200
/* maximum number of stalls */
#define MAXS 200
/* does cow i like stall j */
char likes[MAXC][MAXS];
int ncow; /* number of cows */
int nstall; /* number of stalls */
int stall[MAXC]; /* which stall is cow i assigned to? */
int cow[MAXS]; /* which cow is assigned to stall j? */
int vis[MAXC+MAXS]; /* has the cow/stall been visited */
/* find_cow, find_stall perform a flood fill to determine if there
is a path in the graph from the super source to the super sink
(see max matching algorithm */
/* vis is the location that the flood is done */
/* find_cow tries to find a cow to go with a stall */
/* find_stall tries to find a stall to go with a cow */
int find_stall(int cnum);
int find_cow(int stall)
{
/* if we've already visited here, no need to try again */
if (vis[stall+MAXC]) return 0;
vis[stall+MAXC] =3D 1; /* mark as visited */
/* if this stall isn't assign, then we can go to super sink, and
a path is found! */
if (cow[stall] =3D=3D -1) return 1;
else return find_stall(cow[stall]);
}
int find_stall(int cnum)
{ /* cnum =3D cow number */
int lv; /* loop variable */
/* if we've already visited here, no need to try again */
if (vis[cnum]) return 0;
vis[cnum] =3D 1; /* mark as visited */
/* for each stall that the cow likes, see if there's a path from there
to the super sink */
for (lv =3D 0; lv < nstall; lv++)
if (likes[cnum][lv])
{
if (find_cow(lv))=20
{ /* there's a path, so add that augmenting path by assigning
this cow to stall lv */
stall[cnum] =3D lv;
cow[lv] =3D cnum;
return 1;
}
}
return 0;
}
/* look for an augmenting path */
int find_path(void)
{
int lv;
memset(vis, 0, sizeof(vis));
/* for each cow that is not assigned to a stall there's an edge from
the super source, so see if there's a path using that edge */
for (lv =3D 0; lv < ncow; lv++)
if (stall[lv] =3D=3D -1)
if (find_stall(lv)) return 1;
return 0;
}
int main(int argc, char **argv)
{
FILE *fout, *fin;
int lv; /* loop variable */
int cnt; /* counter used for reading the stalls a cow likes */
int st; /* st number */
if ((fin =3D fopen("stall4.in", "r")) =3D=3D NULL)
{
perror ("fopen fin");
exit(1);
}
if ((fout =3D fopen("stall4.out", "w")) =3D=3D NULL)
{
perror ("fopen fout");
exit(1);
}
fscanf (fin, "%d %d", &ncow, &nstall);
for (lv =3D 0; lv < ncow; lv++)
{
fscanf (fin, "%d", &cnt);
/* read stall numbers */
while (cnt--)
{
fscanf (fin, "%d", &st);
likes[lv][st-1] =3D 1; /* 0-based indexing, so st-1, not st */
}
stall[lv] =3D -1; /* note that the cow is not assigned to a stall */
}
/* for each stall, note it's not assigned a cow */
for (lv =3D 0; lv < nstall; lv++)
cow[lv] =3D -1;
/* max flow algorithm: augment while possible */
for (lv =3D 0; find_path(); lv++)
;
fprintf (fout, "%i\n", lv);
return 0;
}
</STRONG></PRE><BR></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/467ad862639070d9e6113a06.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 4.1.3 Fence Loops =CC=E2=BD=E2', 'USACO 4.1.3 =
Fence Loops =
=CC=E2=BD=E2','/leokan/blog/item/b586bc352214108fa71e12ce.html'];
var post =3D [true,'USACO 4.2.1 Drainage Ditches =CC=E2=BD=E2','USACO =
4.2.1 Drainage Ditches ...', =
'/leokan/blog/item/30aabe1bd7f26f1d8718bf04.html'];
if(pre[0] || post[0]){
document.write('<div =
style=3D"height:5px;line-height:5px;"> </div><div id=3D"in_nav">');
if(pre[0]){
document.write('=C9=CF=D2=BB=C6=AA=A3=BA<a href=3D"' + pre[3] + '" =
title=3D"' + pre[1] + '">' + pre[2] + '</a> ');
}
if(post[0]){
document.write('=CF=C2=D2=BB=C6=AA=A3=BA<a href=3D"' + post[3] + '" =
title=3D"' + post[1] + '">' + post[2] + '</a>');
}
document.write('</div>');
}
/*]]>*/
</SCRIPT>
</DIV>
<DIV class=3Dline></DIV>
<STYLE type=3Dtext/css>#in_related_doc A {
TEXT-DECORATION: none
}
</STYLE>
<DIV id=3Din_related_tmp></DIV>
<SCRIPT language=3Djavascript type=3Dtext/javascript>
/*<![CDATA[*/
function HI_MOD_IN_RELATED_DOC_CALLBACK(arg){
if(arg.length <=3D 1) return false;
var hasMore =3D arg[0];
var D=3Dfunction(A,B){A[A.length]=3DB;}
if(arg.length % 2 =3D=3D 0) D(arg, ["","","",""]);
var html =3D ['<div id=3D"in_related_doc"><div =
class=3D"tit">=CF=E0=B9=D8=CE=C4=D5=C2=A3=BA</div>'];
D(html, '<table cellpadding=3D"0" cellspacing=3D"3" border=3D"0">');
for(var i =3D 1, j =3D arg.length; i < j; i +=3D 2){
D(html, '<tr>');
D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>•</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i][3] + =
'/blog/item/' + arg[i][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i][0] + '">' + arg[i][1] + '</a>');
D(html, new Array(10).join('\u3000'));
D(html, '</td>');
if(arg[i + 1][0] !=3D "")
D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>•</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i + 1][3] + =
'/blog/item/' + arg[i + 1][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i + 1][0] + '">' + arg[i + 1][1] + '</a></td>');
else
D(html, '<td> </td><td> </td>');
D(html, '</tr>');
}
if(hasMore) D(html, '<tr><td colspan=3D"4"><a target=3D"_blank" =
href=3D"/sys/search?pageno=3D1&type=3D7&sort=3D1&word=3DUSACO%204%2E2%2E2=
%20The%20Perfect%20Stall%20%CC%E2%BD%E2&item=3D467ad862639070d9e6113a06">=
=B8=FC=B6=E0>></a></td></tr>');
D(html, '</table></div><div class=3D"line"> </div>');
var div =3D document.getElementById('in_related_tmp');
if(div){
div.innerHTML =3D html.join('');
while(div.firstChild){
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -