📄 usaco 4_2_1 drainage ditches 题解_leokan的blog.mht
字号:
href=3D"http://hi.baidu.com/leokan/album">=CF=E0=B2=E1</A><SPAN>|</SPAN><=
A=20
href=3D"http://hi.baidu.com/leokan/profile">=B8=F6=C8=CB=B5=B5=B0=B8</A> =
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/friends">=BA=C3=D3=D1</A> =
</DIV></DIV>
<DIV class=3Dstage>
<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 4.2.1 Drainage Ditches =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA02=D4=C222=C8=D5 =D0=C7=C6=DA=CE=E5 =
20:07</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 4.2.1 Drainage Ditches</H2>
<DIV class=3Dt_msgfont>Drainage Ditches<BR>Hal Burch <BR>Every =
time it rains=20
on Farmer John's fields, a pond forms over Bessie's favorite =
clover patch.=20
This means that the clover is covered by water for awhile and =
takes quite=20
a long time to regrow. Thus, Farmer John has built a set of =
drainage=20
ditches so that Bessie's clover patch is never covered in water. =
Instead,=20
the water is drained to a nearby stream. Being an ace engineer, =
Farmer=20
John has also installed regulators at the beginning of each ditch, =
so he=20
can control at what rate water flows into that ditch. =
<BR><BR>Farmer John=20
knows not only how many gallons of water each ditch can transport =
per=20
minute but also the exact layout of the ditches, which feed out of =
the=20
pond and into each other and stream in a potentially complex =
network. Note=20
however, that there can be more than one ditch between two =
intersections.=20
<BR><BR>Given all this information, determine the maximum rate at =
which=20
water can be transported out of the pond and into the stream. For =
any=20
given ditch, water flows in only one direction, but there might be =
a way=20
that water can flow in a circle. <BR><BR>PROGRAM NAME: =
ditch<BR>INPUT=20
FORMAT<BR>Line 1: Two space-separated integers, N (0 =
<=3D N=20
<=3D 200) and M (2 <=3D M <=3D 200). N is the number of =
ditches that=20
Farmer John has dug. M is the number of intersections points for =
those=20
ditches. Intersection 1 is the pond. Intersection point M is the=20
stream. <BR>Line 2..N+1: Each of N lines =
contains=20
three integers, Si, Ei, and Ci. Si and Ei (1 <=3D Si, Ei =
<=3D M)=20
designate the intersections between which this ditch flows. Water =
will=20
flow through this ditch from Si to Ei. Ci (0 <=3D Ci <=3D =
10,000,000) is=20
the maximum rate at which water will flow through the=20
ditch. <BR><BR>SAMPLE INPUT (file ditch.in) <BR>5 =
4<BR>1 2=20
40<BR>1 4 20<BR>2 4 20<BR>2 3 30<BR>3 4 10<BR><BR>OUTPUT =
FORMAT<BR>One=20
line with a single integer, the maximum rate at which water may =
emptied=20
from the pond. <BR><BR>SAMPLE OUTPUT (file=20
ditch.out)<BR>50<BR><BR><BR><BR>Drainage Ditches =
<BR><BR>=B2=DD=B5=D8=C5=C5=CB=AE <BR><BR>Hal=20
Burch <BR><BR>=D2=EB by Felicia=20
=
Crazy<BR><BR>=D4=DA=C5=A9=B7=F2=D4=BC=BA=B2=B5=C4=C5=A9=B3=A1=C9=CF=A3=AC=
=C3=BF=B7=EA=CF=C2=D3=EA=A3=AC=B1=B4=DC=E7=D7=EE=CF=B2=BB=B6=B5=C4=C8=FD=D2=
=B6=B2=DD=B5=D8=BE=CD=BB=FD=BE=DB=C1=CB=D2=BB=CC=B6=CB=AE=A1=A3=D5=E2=D2=E2=
=CE=B6=D7=C5=B2=DD=B5=D8=B1=BB=CB=AE=D1=CD=C3=BB=C1=CB=A3=AC=B2=A2=C7=D2=D0=
=A1=B2=DD=D2=AA=BC=CC=D0=F8=C9=FA=B3=A4=BB=B9=D2=AA=BB=A8=CF=E0=B5=B1=B3=A4=
=D2=BB=B6=CE=CA=B1=BC=E4=A1=A3=D2=F2=B4=CB=A3=AC=C5=A9=B7=F2=D4=BC=BA=B2=D0=
=DE=BD=A8=C1=CB=D2=BB=CC=D7=C5=C5=CB=AE=CF=B5=CD=B3=C0=B4=CA=B9=B1=B4=DC=E7=
=B5=C4=B2=DD=B5=D8=C3=E2=B3=FD=B1=BB=B4=F3=CB=AE=D1=CD=C3=BB=B5=C4=B7=B3=C4=
=D5=A3=A8=B2=BB=D3=C3=B5=A3=D0=C4=A3=AC=D3=EA=CB=AE=BB=E1=C1=F7=CF=F2=B8=BD=
=BD=FC=B5=C4=D2=BB=CC=F5=D0=A1=CF=AA=A3=A9=A1=A3=D7=F7=CE=AA=D2=BB=C3=FB=D2=
=BB=C1=F7=B5=C4=BC=BC=CA=A6=A3=AC=C5=A9=B7=F2=D4=BC=BA=B2=D2=D1=BE=AD=D4=DA=
=C3=BF=CC=F5=C5=C5=CB=AE=B9=B5=B5=C4=D2=BB=B6=CB=B0=B2=C9=CF=C1=CB=BF=D8=D6=
=C6=C6=F7=A3=AC=D5=E2=D1=F9=CB=FB=BF=C9=D2=D4=BF=D8=D6=C6=C1=F7=C8=EB=C5=C5=
=CB=AE=B9=B5=B5=C4=CB=AE=C1=F7=C1=BF=A1=A3=20
=
<BR><BR>=C5=A9=B7=F2=D4=BC=BA=B2=D6=AA=B5=C0=C3=BF=D2=BB=CC=F5=C5=C5=CB=AE=
=B9=B5=C3=BF=B7=D6=D6=D3=BF=C9=D2=D4=C1=F7=B9=FD=B5=C4=CB=AE=C1=BF=A3=AC=BA=
=CD=C5=C5=CB=AE=CF=B5=CD=B3=B5=C4=D7=BC=C8=B7=B2=BC=BE=D6=A3=A8=C6=F0=B5=E3=
=CE=AA=CB=AE=CC=B6=B6=F8=D6=D5=B5=E3=CE=AA=D0=A1=CF=AA=B5=C4=D2=BB=D5=C5=CD=
=F8=A3=A9=A1=A3=D0=E8=D2=AA=D7=A2=D2=E2=B5=C4=CA=C7=A3=AC=D3=D0=D0=A9=CA=B1=
=BA=F2=B4=D3=D2=BB=B4=A6=B5=BD=C1=ED=D2=BB=B4=A6=B2=BB=D6=BB=D3=D0=D2=BB=CC=
=F5=C5=C5=CB=AE=B9=B5=A1=A3<BR><BR>=B8=F9=BE=DD=D5=E2=D0=A9=D0=C5=CF=A2=A3=
=AC=BC=C6=CB=E3=B4=D3=CB=AE=CC=B6=C5=C5=CB=AE=B5=BD=D0=A1=CF=AA=B5=C4=D7=EE=
=B4=F3=C1=F7=C1=BF=A1=A3=B6=D4=D3=DA=B8=F8=B3=F6=B5=C4=C3=BF=CC=F5=C5=C5=CB=
=AE=B9=B5=A3=AC=D3=EA=CB=AE=D6=BB=C4=DC=D1=D8=D7=C5=D2=BB=B8=F6=B7=BD=CF=F2=
=C1=F7=B6=AF=A3=AC=D7=A2=D2=E2=BF=C9=C4=DC=BB=E1=B3=F6=CF=D6=D3=EA=CB=AE=BB=
=B7=D0=CE=C1=F7=B6=AF=B5=C4=C7=E9=D0=CE=A1=A3<BR><BR>PROGRAM=20
NAME:ditch<BR><BR>INPUT FORMAT<BR><BR>=B5=DA1=D0=D0: =
=C1=BD=B8=F6=D3=C3=BF=D5=B8=F1=B7=D6=BF=AA=B5=C4=D5=FB=CA=FDN (0 <=3D =
N <=3D=20
200) =BA=CD M (2 <=3D M <=3D=20
=
200)=A1=A3N=CA=C7=C5=A9=B7=F2=D4=BC=BA=B2=D2=D1=BE=AD=CD=DA=BA=C3=B5=C4=C5=
=C5=CB=AE=B9=B5=B5=C4=CA=FD=C1=BF=A3=ACM=CA=C7=C5=C5=CB=AE=B9=B5=BD=BB=B2=
=E6=B5=E3=B5=C4=CA=FD=C1=BF=A1=A3=BD=BB=B5=E31=CA=C7=CB=AE=CC=B6=A3=AC=BD=
=BB=B5=E3M=CA=C7=D0=A1=CF=AA=A1=A3 =
<BR>=B5=DA=B6=FE=D0=D0=B5=BD=B5=DAN+1=D0=D0:=20
=C3=BF=D0=D0=D3=D0=C8=FD=B8=F6=D5=FB=CA=FD=A3=ACSi, Ei, =BA=CD =
Ci=A1=A3Si =BA=CD Ei (1 <=3D Si, Ei <=3D M) =
=D6=B8=C3=F7=C5=C5=CB=AE=B9=B5=C1=BD=B6=CB=B5=C4=BD=BB=B5=E3=A3=AC=D3=EA=CB=
=AE=B4=D3Si=20
=C1=F7=CF=F2Ei=A1=A3Ci (0 <=3D Ci <=3D =
10,000,000)=CA=C7=D5=E2=CC=F5=C5=C5=CB=AE=B9=B5=B5=C4=D7=EE=B4=F3=C8=DD=C1=
=BF=A1=A3 <BR><BR>SAMPLE INPUT=20
(file ditch.in)<BR><BR>5 4<BR>1 2 40<BR>1 4 20<BR>2 4 20<BR>2 3 =
30<BR>3 4=20
10<BR><BR>OUTPUT =
FORMAT<BR><BR>=CA=E4=B3=F6=D2=BB=B8=F6=D5=FB=CA=FD=A3=AC=BC=B4=C5=C5=CB=AE=
=B5=C4=D7=EE=B4=F3=C1=F7=C1=BF=A1=A3<BR><BR>SAMPLE OUTPUT (file=20
ditch.out)<BR><BR>50</DIV>
<HR>
<P><STRONG>USACO 4.2.1 Drainage =
Ditches<BR>=CC=E1=BD=BB=B4=CE=CA=FD:5=B4=CE</STRONG></P>
=
<P><STRONG>=D2=D4=CE=AA=CB=FB=CA=C7=BC=F2=B5=A5=CD=BC,=D6=B1=BD=D3=B8=B3=D6=
=B5=C1=CB,=BA=F3=C0=B4=B6=D4=D7=C5=CA=FD=BE=DD=BF=B4=B2=C5=B7=A2=CF=D6=C1=
=BD=B8=F6=B5=E3=BF=C9=D2=D4=C1=AC=BD=D31=CC=F5=D2=D4=C9=CF=B5=C4=B1=DF,=D3=
=DA=CA=C7=B8=C4=BD=F8=C1=CB=CF=C2,ac.<BR>=BD=AB=D4=AD=CF=C8=CE=D2=D3=C3=B5=
=C4=D7=EE=B4=F3=C1=F7=B8=C4=CE=AA=C4=A3=BF=E9=BB=AF=C1=CB,=BE=CD=CA=C7=B1=
=E4=CE=AA=D2=BB=B8=F6=CB=E6=CA=B1=C4=DC=D3=C3=B5=C4=BA=AF=CA=FD,maxflow(v=
0,vm),=D7=EE=BD=FC=B8=C4=C4=A3=BF=E9=B8=C4=B5=C3=BA=DC=B6=E0,spfa(v0)=D6=AE=
=C0=E0=B5=C4...</STRONG></P>
<P><STRONG>{<BR>TASK:ditch<BR>LANG:PASCAL<BR>}<BR>program=20
ditch;<BR>const<BR> =20
maxn=3D200;<BR>var<BR> =
n,m:integer;<BR> =20
capacity:array[1..maxn,1..maxn] of qword;<BR> =20
contact:array[1..maxn,0..maxn] of integer;<BR>function=20
min(x,y:longint):longint;<BR>begin<BR> if x>y =
then=20
exit(y)<BR> else exit(x);<BR>end;<BR>procedure=20
init;<BR>var<BR> =20
i,x,y,capa:longint;<BR>begin<BR> =20
assign(input,'ditch.in');reset(input);<BR> =20
fillchar(capacity,sizeof(capacity),0);<BR> =20
readln(n,m);<BR> for i:=3D1 to n=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
read(x,y,capa);<BR> =
=20
=
inc(capacity[x,y],capa);<BR> &nb=
sp; =20
=
inc(contact[x,0]);<BR> &nb=
sp; =20
=
contact[x,contact[x,0]]:=3Dy;<BR> &nbs=
p;=20
end;<BR> close(input);<BR>end;<BR>function=20
maxflow(v0,vm:integer):qword;<BR>var<BR> =20
visit:array[1..maxn]of boolean;<BR> =20
pre,flow:array[1..maxn] of qword;<BR> =20
i,jump:longint;<BR> =20
total,max,maxl,increse:qword;<BR>begin<BR> =20
total:=3D0;<BR> while true=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
fillchar(visit,sizeof(visit),0);<BR> &=
nbsp; =20
=
fillchar(flow,sizeof(flow),0);<BR> &nb=
sp; =20
=
fillchar(pre,sizeof(pre),0);<BR>  =
; =20
=
flow[v0]:=3Dmaxlongint;<BR> &nbs=
p; =20
while true=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p; =20
=
max:=3D0;<BR> =
=20
=
maxl:=3D0;<BR>  =
; =20
for i:=3D1 to m=20
=
do<BR> &=
nbsp; =20
if not visit[i] and (flow[i]>max)=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
=
max:=3Dflow[i];<BR> =
&=
nbsp; =20
=
maxl:=3Di;<BR>  =
; =
=20
=
end;<BR>  =
; =20
if (maxl=3D0)or(maxl=3Dvm) then=20
=
break;<BR> &nb=
sp; =20
=
visit[maxl]:=3Dtrue;<BR> &=
nbsp; =20
for i:=3D1 to m=20
=
do<BR> &=
nbsp; =20
if flow[i]<min(max,capacity[maxl,i])=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
=
pre[i]:=3Dmaxl;<BR> =
&=
nbsp; =20
=
flow[i]:=3Dmin(max,capacity[maxl,i]);<BR> &n=
bsp; &nb=
sp; =20
=
end;<BR>  =
; =20
=
end;<BR>  =
;=20
if maxl=3D0 then=20
=
break;<BR> &nb=
sp;=20
=
increse:=3Dflow[vm];<BR> &=
nbsp; =20
=
inc(total,increse);<BR> &n=
bsp; =20
=
i:=3Dvm;<BR> &=
nbsp;=20
while i>1=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p; =20
=
jump:=3Dpre[i];<BR> =
=20
=
dec(capacity[jump,i],increse);<BR> &nb=
sp; &nbs=
p;=20
=
inc(capacity[i,jump],increse);<BR> &nb=
sp; &nbs=
p;=20
=
i:=3Djump;<BR>  =
; =20
end;<BR> =20
end;<BR> exit(total);<BR>end;<BR>procedure=20
work;<BR>begin<BR> =20
assign(output,'ditch.out');rewrite(output);<BR> =20
writeln(maxflow(1,m));<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.</STRONG></P>
<P>
<P></P>
<P><STRONG>USACO=B5=C4=CB=E3=B7=A8=BA=DC=BC=F2=BD=E0</STRONG></P>
<P><STRONG>This is a basic maximum flow problem. Just use the max =
flow=20
algorithm. </STRONG></P><PRE><STRONG>#include <stdio.h>
#include <string.h>
#define MAXI 200
/* total drain amount between intersection points */
int drain[MAXI][MAXI];
int nint; /* number of intersection points */
int cap[MAXI]; /* amount of flow that can get to each node */
int vis[MAXI]; /* has this node been visited by Dijkstra's yet? */
int src[MAXI]; /* the previous node on the path from the source to here =
*/
int augment(void)
{ /* run a Dijkstra's varient to find maximum augmenting path */
int lv;
int mloc, max;
int t;
memset(cap, 0, sizeof(cap));
memset(vis, 0, sizeof(vis));
cap[0] =3D 2000000000;
while (1)
{
/* find maximum unvisited node */
max =3D 0;
mloc =3D -1;
for (lv =3D 0; lv < nint; lv++)
if (!vis[lv] && cap[lv] > max)
{
max =3D cap[lv];
mloc =3D lv;
}
if (mloc =3D=3D -1) return 0;
if (mloc =3D=3D nint-1) break; /* max is the goal, we're done */
vis[mloc] =3D -1; /* mark as visited */
/* update neighbors, if going through this node improves the
capacity */
for (lv =3D 0; lv < nint; lv++)
if (drain[mloc][lv] > cap[lv] && max > cap[lv])
{
cap[lv] =3D drain[mloc][lv];
if (cap[lv] > max) cap[lv] =3D max;
src[lv] =3D mloc;
}
}
max =3D cap[nint-1];
/* augment path, starting at end */
for (lv =3D nint-1; lv > 0; lv =3D src[lv])
{
t =3D src[lv];
drain[t][lv] -=3D max;
drain[lv][t] +=3D max;
}
return max;
}
int main(int argc, char **argv)
{
FILE *fout, *fin;
int lv;
int num;
int p1, p2, c;
if ((fin =3D fopen("ditch.in", "r")) =3D=3D NULL)
{
perror ("fopen fin");
exit(1);
}
if ((fout =3D fopen("ditch.out", "w")) =3D=3D NULL)
{
perror ("fopen fout");
exit(1);
}
fscanf (fin, "%d %d", &num, &nint);
while (num--)
{
fscanf (fin, "%d %d %d", &p1, &p2, &c);
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -