📄 usaco 3_2_6 sweet butter 题解_leokan的blog.mht
字号:
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 3.2.6 Sweet Butter =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA02=D4=C205=C8=D5 =D0=C7=C6=DA=B6=FE =
20:10</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 3.2.6 Sweet Butter</H2>
<DIV class=3Dt_msgfont>Sweet Butter<BR>Greg Galperin -- =
2001<BR>Farmer John=20
has discovered the secret to making the sweetest butter in all of=20
Wisconsin: sugar. By placing a sugar cube out in the pastures, he =
knows=20
the N (1 <=3D N <=3D 500) cows will lick it and thus will =
produce=20
super-sweet butter which can be marketed at better prices. Of =
course, he=20
spends the extra money on luxuries for the cows. <BR><BR>FJ is a =
sly=20
farmer. Like Pavlov of old, he knows he can train the cows to go =
to a=20
certain pasture when they hear a bell. He intends to put the sugar =
there=20
and then ring the bell in the middle of the afternoon so that the=20
evening's milking produces perfect milk. <BR><BR>FJ knows each cow =
spends=20
her time in a given pasture (not necessarily alone). Given the =
pasture=20
location of the cows and a description of the paths the connect =
the=20
pastures, find the pasture in which to place the sugar cube so =
that the=20
total distance walked by the cows when FJ rings the bell is =
minimized. FJ=20
knows the fields are connected well enough that some solution is =
always=20
possible. <BR><BR>PROGRAM NAME: butter<BR>INPUT FORMAT<BR>Line 1: =
Three=20
space-separated integers: N, the number of pastures: P (2 <=3D =
P <=3D=20
800), and the number of connecting paths: C (1 <=3D C <=3D =
1,450). Cows=20
are uniquely numbered 1..N. Pastures are uniquely numbered 1..P. =
<BR>Lines=20
2..N+1: Each line contains a single integer that is the pasture =
number in=20
which a cow is grazing. Cow i's pasture is <SPAN class=3Dt_tag=20
href=3D"tag.php?name=3Dlis">lis</SPAN>ted on line i+1. <BR>Lines =
N+2..N+C+1:=20
Each line contains three space-separated integers that describe a =
single=20
path that connects a pair of pastures and its length. Paths may be =
traversed in either direction. No pair of pastures is directly =
connected=20
by more than one path. The first two integers are in the range =
1..P; the=20
third integer is in the range (1..225). <BR>SAMPLE INPUT (file=20
butter.in)<BR>3 4 5<BR>2<BR>3<BR>4<BR>1 2 1<BR>1 3 5<BR>2 3 7<BR>2 =
4=20
3<BR>3 4 5<BR><BR><BR>INPUT DETAILS<BR>This diagram shows the =
connections=20
geometrically: <BR> P2 <BR>P1 =
@--1--@=20
C1<BR> \ |\<BR> \ | =
\<BR> =20
5 7 3<BR> \ =
|=20
\<BR> \| \ C3<BR> C2=20
@--5--@<BR> P3 P4<BR><BR>OUTPUT =
FORMAT<BR>Line 1:=20
A single integer that is the minimum distance the cows must walk =
to a=20
pasture with a sugar cube. <BR>SAMPLE OUTPUT (file butter.out)=20
<BR>8<BR><BR>OUTPUT DETAILS:<BR><BR>Putting the cube in pasture 4 =
means:=20
cow 1 walks 3 units; cow 2 walks 5<BR>units; cow 3 walks 0 units =
-- a=20
total of 8.<BR><BR><BR><BR>Sweet =
Butter<BR>=CF=E3=CC=F0=B5=C4=BB=C6=D3=CD <BR><BR><BR>Greg Galperin=20
-- 2001<BR><BR>=D2=EB by=20
=
kd<BR><BR>=C5=A9=B7=F2John=B7=A2=CF=D6=D7=F6=B3=F6=C8=AB=CD=FE=CB=B9=BF=B5=
=D0=C1=D6=DD=D7=EE=CC=F0=B5=C4=BB=C6=D3=CD=B5=C4=B7=BD=B7=A8=A3=BA=CC=C7=A1=
=A3=B0=D1=CC=C7=B7=C5=D4=DA=D2=BB=C6=AC=C4=C1=B3=A1=C9=CF=A3=AC=CB=FB=D6=AA=
=B5=C0N=A3=A81<=3DN<=3D500=A3=A9=D6=BB=C4=CC=C5=A3=BB=E1=B9=FD=C0=B4=
=CC=F2=CB=FC=A3=AC=D5=E2=D1=F9=BE=CD=C4=DC=D7=F6=B3=F6=C4=DC=C2=F4=BA=C3=BC=
=DB=C7=AE=B5=C4=B3=AC=CC=F0=BB=C6=D3=CD=A1=A3=B5=B1=C8=BB=A3=AC=CB=FB=BD=AB=
=B8=B6=B3=F6=B6=EE=CD=E2=B5=C4=B7=D1=D3=C3=D4=DA=C4=CC=C5=A3=C9=CF=A1=A3 =
<BR><BR> =20
=
=C5=A9=B7=F2John=BA=DC=BD=C6=BB=AB=A1=A3=CF=F1=D2=D4=C7=B0=B5=C4Pavlov=A3=
=AC=CB=FB=D6=AA=B5=C0=CB=FB=BF=C9=D2=D4=D1=B5=C1=B7=D5=E2=D0=A9=C4=CC=C5=A3=
=A3=AC=C8=C3=CB=FC=C3=C7=D4=DA=CC=FD=B5=BD=C1=E5=C9=F9=CA=B1=C8=A5=D2=BB=B8=
=F6=CC=D8=B6=A8=B5=C4=C4=C1=B3=A1=A1=A3=CB=FB=B4=F2=CB=E3=BD=AB=CC=C7=B7=C5=
=D4=DA=C4=C7=C0=EF=C8=BB=BA=F3=CF=C2=CE=E7=B7=A2=B3=F6=C1=E5=C9=F9=A3=AC=D2=
=D4=D6=C1=CB=FB=BF=C9=D2=D4=D4=DA=CD=ED=C9=CF=BC=B7=C4=CC=A1=A3=20
<BR><BR> =20
=
=C5=A9=B7=F2John=D6=AA=B5=C0=C3=BF=D6=BB=C4=CC=C5=A3=B6=BC=D4=DA=B8=F7=D7=
=D4=CF=B2=BB=B6=B5=C4=C4=C1=B3=A1=A3=A8=D2=BB=B8=F6=C4=C1=B3=A1=B2=BB=D2=BB=
=B6=A8=D6=BB=D3=D0=D2=BB=CD=B7=C5=A3=A3=A9=A1=A3=B8=F8=B3=F6=B8=F7=CD=B7=C5=
=A3=D4=DA=B5=C4=C4=C1=B3=A1=BA=CD=C4=C1=B3=A1=BC=E4=B5=C4=C2=B7=CF=DF=A3=AC=
=D5=D2=B3=F6=CA=B9=CB=F9=D3=D0=C5=A3=B5=BD=B4=EF=B5=C4=C2=B7=B3=CC=BA=CD=D7=
=EE=B6=CC=B5=C4=C4=C1=B3=A1=A3=A8=CB=FB=BD=AB=B0=D1=CC=C7=B7=C5=D4=DA=C4=C7=
=A3=A9<BR><BR><BR>PROGRAM=20
NAME: butter<BR>INPUT FORMAT<BR>=B5=DA=D2=BB=D0=D0:=20
=
=C8=FD=B8=F6=CA=FD=A3=BA=C4=CC=C5=A3=CA=FDN=A3=AC=C4=C1=B3=A1=CA=FD=A3=A8=
2<=3DP<=3D800=A3=A9=A3=AC=C4=C1=B3=A1=BC=E4=B5=C0=C2=B7=CA=FDC(1<=
;=3DC<=3D1450)<BR><BR>=B5=DA=B6=FE=D0=D0=B5=BD=B5=DAN+1=D0=D0:=20
=
1=B5=BDN=CD=B7=C4=CC=C5=A3=CB=F9=D4=DA=B5=C4=C4=C1=B3=A1=BA=C5<BR><BR>=B5=
=DAN+2=D0=D0=B5=BD=B5=DAN+C+1=D0=D0=A3=BA=20
=
=C3=BF=D0=D0=D3=D0=C8=FD=B8=F6=CA=FD=A3=BA=CF=E0=C1=AC=B5=C4=C4=C1=B3=A1A=
=A1=A2B=A3=AC=C1=BD=C4=C1=B3=A1=BC=E4=BE=E0=C0=EBD=A3=A81<=3DD<=3D2=
55=A3=A9=A3=AC=B5=B1=C8=BB,=C1=AC=BD=D3=CA=C7=CB=AB=CF=F2=B5=C4<BR><BR>SA=
MPLE INPUT=20
(file butter.in)<BR>3 4 5<BR>2<BR>3<BR>4<BR>1 2 1<BR>1 3 5<BR>2 3 =
7<BR>2 4=20
3<BR>3 4 5<BR>{=D1=F9=C0=FD=CD=BC=D0=CE<BR> =
P2 <BR>P1=20
@--1--@ C1<BR> \ |\<BR> \ |=20
\<BR> 5 7 3<BR> =20
\ | \<BR> \| \=20
C3<BR> C2 @--5--@<BR> P3=20
P4<BR>}<BR>OUTPUT FORMAT<BR> =D2=BB=D0=D0 =20
=
=CA=E4=B3=F6=C4=CC=C5=A3=B1=D8=D0=EB=D0=D0=D7=DF=B5=C4=D7=EE=D0=A1=B5=C4=BE=
=E0=C0=EB=BA=CD<BR><BR>SAMPLE OUTPUT (file butter.out)<BR> =20
8<BR>{=CB=B5=C3=F7=A3=BA<BR> =
=B7=C5=D4=DA4=BA=C5=C4=C1=B3=A1=D7=EE=D3=C5<BR>}</DIV>
<P></P>
<HR>
<P></P>
<P><STRONG>USACO 3.2.6 Sweet =
Butter<BR>=CC=E1=BD=BB=B4=CE=CA=FD:2=B4=CE</STRONG></P>
=
<P><STRONG>=D7=D4=BC=BA=C0=ED=BD=E2SPFA=D4=D9=D7=F6=C1=CB=D2=BB=B4=CE,=B8=
=D0=BE=F5=D3=D0=BA=DC=B4=F3=CA=D5=BB=F1,=B5=AB=CA=C7=C8=D4=D3=D0=D2=BB=B5=
=E3=B2=BB=C3=F7=B0=D7:=D2=D1=BE=AD=D4=DA=B6=D3=C1=D0=D6=D0=B5=C4=B5=E3=B5=
=BD=B5=D7=D2=AA=B2=BB=D2=AA=B8=FC=D0=C2,=C2=B7=B9=FD=B5=C4=B8=E6=CB=DF=CE=
=D2=CF=C2</STRONG></P>
=
<P><STRONG>[=B1=E0=BC=AD=CE=C4=D5=C2:=D2=D1=BE=AD=C3=F7=B0=D7=C1=CB,=D6=BB=
=C4=DC=B8=FC=D0=C2=B5=A5=CF=F2=B5=C4]</STRONG></P>
=
<P><STRONG>=B2=BB=B9=DC=D4=F5=C3=B4=CB=B5,=B5=C3=B5=BD=C1=CB=D7=D4=BC=BA=B5=
=C4=D2=BB=B8=F6SPFA=B3=CC=D0=F2</STRONG></P>
<P><STRONG>{<BR>TASK:butter<BR>LANG:PASCAL<BR>}<BR>program=20
butter;<BR>const<BR> =
maxn=3D800;<BR> =20
maxq=3Dmaxn shl 1;<BR>var<BR> =20
n,p,c:integer;<BR> map:array[1..maxn,1..maxn]of=20
integer;<BR> dis:array[1..maxn,1..maxn] of=20
longint;<BR> cowin:array[0..maxn] of=20
integer;<BR> connect:array[1..maxn,0..maxn] of=20
integer;<BR>procedure init;<BR>var<BR> =20
i,x,y,distance:integer;<BR>begin<BR> =20
assign(input,'butter.in');reset(input);<BR> =20
fillchar(cowin,sizeof(cowin),0);<BR> =20
fillchar(connect,sizeof(connect),0);<BR> =20
fillchar(map,sizeof(map),255);<BR> =20
readln(n,p,c);<BR> for i:=3D1 to n=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
inc(cowin[0]);<BR> &=
nbsp; =20
=
readln(cowin[cowin[0]]);<BR> =20
end;<BR> for i:=3D1 to c=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
readln(x,y,distance);<BR> =
=20
if (map[x,y]=3D-1)or (distance<map[x,y])=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
map[x,y]:=3Ddistance;<BR> =
=20
=
map[y,x]:=3Ddistance;<BR> =
=20
=
end;<BR>  =
;=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 p=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
map[i,i]:=3D0;<BR> &=
nbsp; =20
dis[i,i]:=3D0;<BR> =20
end;<BR> close(input);<BR>end;<BR>procedure=20
spfa(v0:integer);<BR>var<BR> =20
i,now,open,close:integer;<BR> =
queue:array[1..maxq] of=20
integer;<BR> inqueue:array[1..maxn] of=20
boolean;<BR>begin<BR> =20
fillchar(inqueue,sizeof(inqueue),0);<BR> =20
fillchar(queue,sizeof(queue),0);<BR> =20
fillchar(dis[v0],sizeof(dis[v0]),255);<BR> =20
dis[v0,v0]:=3D0;<BR> =
queue[1]:=3Dv0;<BR> =20
inqueue[v0]:=3Dtrue;<BR> =
open:=3D0;<BR> =20
close:=3D1;<BR> while close<>open=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
inc(open);<BR>  =
; =20
if open>maxq then=20
=
dec(open,maxq);<BR> =
=20
=
now:=3Dqueue[open];<BR> &n=
bsp; =20
=
inqueue[now]:=3Dfalse;<BR>  =
; =20
for i:=3D1 to connect[now,0]=20
=
do<BR> &=
nbsp; =20
if=20
=
(dis[v0,connect[now,i]]=3D-1)or(dis[v0,now]+map[now,connect[now,i]]<di=
s[v0,connect[now,i]])=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p;  =
;=20
=
dis[v0,connect[now,i]]:=3Ddis[v0,now]+map[now,connect[now,i]];<BR> &=
nbsp; &n=
bsp; =20
if not inqueue[connect[now,i]]=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
=
inc(close);<BR> &nbs=
p;  =
; =20
if close>maxq then=20
=
dec(close,maxq);<BR>  =
; =
=20
=
queue[close]:=3Dconnect[now,i];<BR> &n=
bsp; &nb=
sp; &nbs=
p;=20
=
inqueue[connect[now,i]]:=3Dtrue;<BR> &=
nbsp; &n=
bsp; =20
=
end;<BR>  =
; =20
end;<BR> =20
end;<BR>end;<BR>procedure work;<BR>var<BR> =20
i,j:integer;<BR> =20
min,sum:longint;<BR>begin<BR> =20
assign(output,'butter.out');rewrite(output);<BR> =
for=20
i:=3D1 to cowin[0] =
do<BR> =20
spfa(cowin[i]);<BR> =20
min:=3Dmaxlongint;<BR> for i:=3D1 to p=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
sum:=3D0;<BR> =
=20
for j:=3D1 to cowin[0]=20
=
do<BR> &=
nbsp; =20
=
inc(sum,dis[cowin[j],i]);<BR> &n=
bsp; =20
if min>sum then =
min:=3Dsum;<BR> =20
end;<BR> writeln(min);<BR> =
{for i:=3D1=20
to p do<BR> =20
=
begin<BR> &nbs=
p;=20
for j:=3D1 to p=20
=
do<BR> &=
nbsp; =20
write(dis[i,j],'=20
=
');<BR> =
=20
writeln;<BR> end;=20
}<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=B7=D6=CE=F6,=B6=D1=D3=C5=BB=AF=B5=C4dijkstra</STRO=
NG></P>
<P><STRONG>We approach this problem directly, by calculating the =
distance=20
from each cow to each pasture. Once this is done, we will simply =
have to=20
sum the distances for each cow to get the total cost of putting =
the sugar=20
cube at a given pasture. The key to a fast distance calculation is =
that=20
our graph is quite sparse. Thus, we use Dijkstra with a heap to =
calculate=20
the distance from a given cow to all pastures. This requires on =
the order=20
of N*C*log(P), or about 7,000,000, =
operations.</STRONG></P><PRE><STRONG>#include <stdio.h>
#include <string.h>
const int BIG =3D 1000000000;
const int MAXV =3D 800;
const int MAXC =3D 500;
const int MAXE =3D 1450;
int cows;
int v,e;
int cow_pos[MAXC];
int degree[MAXV];
int con[MAXV][MAXV];
int cost[MAXV][MAXV];
int dist[MAXC][MAXV];
int heapsize;
int heap_id[MAXV];
int heap_val[MAXV];
int heap_lookup[MAXV];
bool validheap(void){
for(int i =3D 0; i < heapsize; ++i){
if(!(0 <=3D heap_id[i] && heap_id[i] < v)){
return(false);
}
if(heap_lookup[heap_id[i]] !=3D i){
return(false);
}
}
return(true);
}
void heap_swap(int i, int j){
int s;
s =3D heap_val[i];
heap_val[i] =3D heap_val[j];
heap_val[j] =3D s;
heap_lookup[heap_id[i]] =3D j;
heap_lookup[heap_id[j]] =3D i;
s =3D heap_id[i];
heap_id[i] =3D heap_id[j];
heap_id[j] =3D s;
}
void heap_up(int i){
if(i > 0 && heap_val[(i-1) / 2] > heap_val[i]){
heap_swap(i, (i-1)/2);
heap_up((i-1)/2);
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -