📄 usaco 2_3_5 controlling companies 题解_leokan的blog.mht
字号:
<DIV class=3Ddesc></DIV>
<DIV id=3Dtabline></DIV>
<DIV id=3Dtab><A href=3D"http://hi.baidu.com/leokan">=D6=F7=D2=B3</A><A =
class=3Don=20
href=3D"http://hi.baidu.com/leokan/blog">=B2=A9=BF=CD</A><A=20
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> =
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/modify/spbasic/0">=C9=E8=D6=C3</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>
<DIV class=3Dmodopt><A class=3Dmodact=20
href=3D"http://hi.baidu.com/leokan/creat/blog/"><IMG=20
src=3D"http://img.baidu.com/hi/img/ico_postnew.gif" =
align=3DabsMiddle=20
border=3D0>=D0=B4=D0=C2=CE=C4=D5=C2</A></DIV></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 2.3.5 Controlling Companies =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C230=C8=D5 =D0=C7=C6=DA=C8=FD =
13:20</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 2.3.5 Controlling Companies</H2>
<DIV class=3Dt_msgfont>Controlling Companies<BR><BR>Some companies =
are=20
partial owners of other companies because they have acquired part =
of their=20
total shares of stock. For example, Ford owns 12% of Mazda. It is =
said=20
that a company A controls company B if at least one of the =
following=20
conditions is satisfied: <BR><BR>Company A =3D Company B =
<BR>Company A owns=20
more than 50% of Company B <BR>Company A controls K (K >=3D 1) =
companies=20
denoted C1, ..., CK with each company Ci owning xi% of company B =
and x1 +=20
.... + xK > 50%. <BR>Given a <SPAN class=3Dt_tag=20
href=3D"tag.php?name=3Dlis">lis</SPAN>t of triples (i,j,p) which =
denote=20
company i owning p% of company j, calculate all the pairs (h,s) in =
which=20
company h controls company s. There are at most 100 companies.=20
<BR><BR>Write a program to read the list of triples (i,j,p) where =
i, j and=20
p are positive integers all in the range (1..100) and find all the =
pairs=20
(h,s) so that company h controls company s. <BR><BR>PROGRAM NAME:=20
concom<BR>INPUT FORMAT<BR>Line 1: n, the number of =
input=20
triples to follow <BR>Line 2..n+1: Three integers per =
line as=20
a triple (i,j,p) described above. <BR><BR>SAMPLE INPUT =
(file=20
concom.in) <BR>3<BR>1 2 80<BR>2 3 80<BR>3 1 20<BR><BR>OUTPUT=20
FORMAT<BR>List 0 or more companies that control other companies. =
Each line=20
contains two integers that denote that the company whose number is =
the=20
first integer controls the company whose number is the second =
integer.=20
Order the lines in ascending order of the first integer (and =
ascending=20
order of the second integer to break ties). Do not print that a =
company=20
controls itself. <BR>SAMPLE OUTPUT (file concom.out)<BR>1 2<BR>1 =
3<BR>2=20
3<BR><BR><BR><BR>Controlling =
Companies<BR><BR>=BF=D8=D6=C6=B9=AB=CB=BE<BR><BR>=D2=EB by=20
=
TinyTony<BR><BR>=D3=D0=D0=A9=B9=AB=CB=BE=CA=C7=C6=E4=CB=FB=B9=AB=CB=BE=B5=
=C4=B2=BF=B7=D6=D3=B5=D3=D0=D5=DF=A3=AC=D2=F2=CE=AA=CB=FB=C3=C7=BB=F1=B5=C3=
=C1=CB=C6=E4=CB=FB=B9=AB=CB=BE=B7=A2=D0=D0=B5=C4=B9=C9=C6=B1=B5=C4=D2=BB=B2=
=BF=B7=D6=A1=A3=C0=FD=C8=E7=A3=AC=B8=A3=CC=D8=B9=AB=CB=BE=D3=B5=D3=D0=C2=ED=
=D7=D4=B4=EF=B9=AB=CB=BE12%=B5=C4=B9=C9=C6=B1=A1=A3=BE=DD=CB=B5=A3=AC=C8=E7=
=B9=FB=D6=C1=C9=D9=C2=FA=D7=E3=C1=CB=D2=D4=CF=C2=CC=F5=BC=FE=D6=AE=D2=BB=A3=
=AC=B9=AB=CB=BEA=BE=CD=BF=C9=D2=D4=BF=D8=D6=C6=B9=AB=CB=BEB=C1=CB=A3=BA<B=
R><BR>=B9=AB=CB=BEA=20
=3D =B9=AB=CB=BEB=A1=A3 =
<BR>=B9=AB=CB=BEA=D3=B5=D3=D0=B4=F3=D3=DA50%=B5=C4=B9=AB=CB=BEB=B5=C4=B9=C9=
=C6=B1=A1=A3 <BR>=B9=AB=CB=BEA=BF=D8=D6=C6K(K >=3D =
1)=B8=F6=B9=AB=CB=BE=A3=AC=BC=C7=CE=AAC1, ...,=20
=
CK=A3=AC=C3=BF=B8=F6=B9=AB=CB=BECi=D3=B5=D3=D0xi%=B5=C4=B9=AB=CB=BEB=B5=C4=
=B9=C9=C6=B1=A3=AC=B2=A2=C7=D2x1+ .... + xK > 50%=A1=A3 =
<BR>=C4=E3=BD=AB=B1=BB=B8=F8=D3=E8=D2=BB=CF=B5=C1=D0=B5=C4=C8=FD<SPAN=20
class=3Dt_tag=20
=
href=3D"tag.php?name=3D%B6%D4%CA%FD">=B6=D4=CA=FD</SPAN>=A3=A8i=A3=ACj=A3=
=ACp=A3=A9=A3=AC=B1=ED=C3=F7=B9=AB=CB=BEi=CF=ED=D3=D0=B9=AB=CB=BEj=B5=C4p=
%=B5=C4=B9=C9=C6=B1=A1=A3=BC=C6=CB=E3=CB=F9=D3=D0=B5=C4=CA=FD=B6=D4=A3=A8=
h=A3=ACs=A3=A9=A3=AC=B1=ED=C3=F7=B9=AB=CB=BEh=BF=D8=D6=C6=B9=AB=CB=BEs=A1=
=A3=D6=C1=B6=E0=D3=D0100=B8=F6=B9=AB=CB=BE=A1=A3<BR><BR>=D0=B4=D2=BB=B8=F6=
=B3=CC=D0=F2=B6=C1=C8=EB=C8=FD=B6=D4=CA=FD=A3=A8i=A3=ACj=A3=ACp=A3=A9=A3=AC=
i=A3=ACj=BA=CDp=CA=C7=B6=BC=D4=DA=B7=B6=CE=A7(1..100)=B5=C4=D5=FD=D5=FB=CA=
=FD=A3=AC=B2=A2=C7=D2=D5=D2=B3=F6=CB=F9=D3=D0=B5=C4=CA=FD=B6=D4=A3=A8h=A3=
=ACs=A3=A9=A3=AC=CA=B9=B5=C3=B9=AB=CB=BEh=BF=D8=D6=C6=B9=AB=CB=BEs=A1=A3<=
BR><BR>PROGRAM=20
NAME: concom<BR><BR>INPUT FORMAT<BR><BR>=B5=DA=D2=BB=D0=D0=A3=BA =
N=A3=AC=B1=ED=C3=F7=BD=D3=CF=C2=C0=B4=C8=FD=B6=D4=CA=FD=B5=C4=CA=FD=C1=BF=
=A1=A3 <BR>=B5=DA=B6=FE=D0=D0=B5=BD=B5=DAN+1=D0=D0=A3=BA=20
=
=C3=BF=D0=D0=C8=FD=B8=F6=D5=FB=CA=FD=D7=F7=CE=AA=D2=BB=B8=F6=C8=FD=B6=D4=CA=
=FD=A3=A8i=A3=ACj=A3=ACp=A3=A9=A3=AC=C8=E7=C9=CF=CE=C4=CB=F9=CA=F6=A1=A3 =
<BR><BR>SAMPLE INPUT (file concom.in)=20
<BR><BR>3<BR>1 2 80<BR>2 3 80<BR>3 1 20<BR><BR>OUTPUT=20
=
FORMAT<BR><BR>=CA=E4=B3=F6=C1=E3=B8=F6=BB=F2=B8=FC=B6=E0=B8=F6=B5=C4=BF=D8=
=D6=C6=C6=E4=CB=FB=B9=AB=CB=BE=B5=C4=B9=AB=CB=BE=A1=A3=C3=BF=D0=D0=B0=FC=C0=
=A8=C1=BD=B8=F6=D5=FB=CA=FD=B1=ED=C3=F7=D0=F2=BA=C5=CE=AA=B5=DA=D2=BB=B8=F6=
=D5=FB=CA=FD=B5=C4=B9=AB=CB=BE=BF=D8=D6=C6=C1=CB=D0=F2=BA=C5=CE=AA=B5=DA=B6=
=FE=B8=F6=D5=FB=CA=FD=B5=C4=B9=AB=CB=BE=A1=A3=BD=AB=CA=E4=B3=F6=B5=C4=C3=BF=
=D0=D0=D2=D4=B5=DA=D2=BB=B8=F6=CA=FD=D7=D6=C9=FD=D0=F2=C5=C5=C1=D0=A3=A8=B2=
=A2=C7=D2=B5=DA=B6=FE=B8=F6=CA=FD=D7=D6=D2=B2=C9=FD=D0=F2=C5=C5=C1=D0=C0=B4=
=B1=DC=C3=E2=B2=A2=C1=D0=A3=A9=A1=A3=C7=EB=B2=BB=D2=AA=CA=E4=B3=F6=BF=D8=D6=
=C6=D7=D4=BC=BA=B5=C4=B9=AB=CB=BE=A1=A3<BR><BR>SAMPLE=20
OUTPUT (file concom.out)<BR><BR>1 2<BR>1 3<BR>2 3</DIV>
<P></P>
<HR>
<P></P>
<P><STRONG>USACO 2.2.5 Controlling Companies =
<BR>=CC=E1=BD=BB=B4=CE=CA=FD:1=B4=CE</STRONG></P>
=
<P><STRONG>=B5=DA=D2=BB=B4=CE=CC=E1=BD=BB0.9=C3=EB=B9=FD,=D4=D9=BC=F4=D2=BB=
=CF=C20.5=C3=EB=B9=FD,=B9=C0=BC=C6=B8=C4=D2=BB=CF=C2=CA=FD=BE=DD=BD=E1=B9=
=B9=BF=C9=D2=D4=D4=D9=BF=EC=D2=BB=B1=B6=B0=C9,=D4=AD=CF=C8=BF=B4=B4=ED=CC=
=E2=C1=CB,=D2=D4=CE=AAn=CA=C7=D6=B8=B9=AB=CB=BE=B5=C4=B1=E0=BA=C5=B5=C4=D7=
=EE=B4=F3,=C7=D2=B1=E0=BA=C5=B0=B4=CB=B3=D0=F2=C5=C5=C1=D0,=BE=CD=D3=C3=C1=
=CB=C1=DA=BD=D3=BE=D8=D5=F3=B1=ED=CA=BE=B9=AB=CB=BE=D6=AE=BC=E4=B5=C4=B9=D8=
=CF=B5,=D5=E2=CC=E2=B9=C0=BC=C6=D3=C3=C1=DA=BD=D3=B1=ED=BF=C9=D2=D4=BF=EC=
=BA=DC=B6=E0,=D3=A6=CE=AA=B2=BB=D3=C3=C3=B6=BE=D9=C3=BF=B8=F6=B5=E3=C9=F5=
=D6=C1=CA=C7=B2=BB=B4=E6=D4=DA=B5=C4=B5=E3.=D6=D8=B8=B4=B8=FC=D0=C2=B9=AB=
=CB=BE=D3=EB=B9=AB=CB=BE=D6=AE=BC=E4=B9=D8=CF=B5,=D6=B1=B5=BD=C3=BB=B5=C3=
=B8=FC=D0=C2=CE=AA=D6=B9=CA=E4=B3=F6.</STRONG></P>
<P><STRONG>{<BR>TASK:concom<BR>LANG:PASCAL<BR>}<BR>program=20
concom;<BR>var<BR> =
control:array[1..100,1..100]of=20
boolean;<BR> map:array[1..100,1..100] of=20
integer;<BR> have:array[1..100] of=20
integer;<BR> {done:array[1..100] of=20
boolean; }<BR> =
n:integer;<BR>procedure=20
init;<BR>var<BR> =20
i,x,y,pr:integer;<BR>begin<BR> =20
assign(input,'concom.in');reset(input);<BR> =20
readln(n);<BR> =20
fillchar(map,sizeof(map),0);<BR> =20
fillchar(have,sizeof(have),0);<BR> for i:=3D1 to =
n=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
readln(x,y,pr);<BR> =
=20
=
map[x,y]:=3Dpr;<BR> =
=20
if pr>have[x] then=20
have[x]:=3Dpr;<BR> =20
end;<BR> =20
fillchar(control,sizeof(control),false);<BR> for =
i:=3D1 to=20
100 do<BR> =20
control[i,i]:=3Dtrue;<BR> =20
close(input);<BR>end;<BR>procedure =
work;<BR>var<BR> =20
noon:boolean;<BR> =
i,j,k:integer;<BR> =20
sum:integer;<BR>begin<BR> =20
noon:=3Dfalse;<BR> while not noon=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
noon:=3Dtrue;<BR> &n=
bsp; =20
for i:=3D1 to 100 do if have[i]>50=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
for j:=3D1 to 100 do if not control[i,j]=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
=
sum:=3D0;<BR> =
&=
nbsp; =20
for k:=3D1 to 100=20
=
do<BR> &=
nbsp; &n=
bsp; =20
if control[i,k]=20
=
then<BR>  =
; =
=
=
inc(sum,map[k,j]);<BR> &nb=
sp; &nbs=
p; =20
if (sum>50)=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =
=20
=
control[i,j]:=3Dtrue;<BR> =
&=
nbsp; &n=
bsp; =20
=
noon:=3Dfalse;<BR> &=
nbsp; &n=
bsp; =20
=
end;<BR>  =
; =
=20
=
end;<BR>  =
; =20
end;<BR> =20
end;<BR> =20
assign(output,'concom.out');rewrite(output);<BR> =
for=20
i:=3D1 to 100 do<BR> for =
j:=3D1 to=20
100=20
=
do<BR> =
if (i<>j)and control[i,j]=20
=
then<BR>  =
; =20
writeln(i,' ',j);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.</STRONG></P>
<P><BR>
<P></P>
<P><STRONG></STRONG></P>
<P><STRONG>The method used here to solve the problem is as =
follows. We=20
keep track of which companies control which other companies, and =
every=20
time we hear that so and so owns this much percent of so and so, =
we update=20
our information. </STRONG></P>
<P><STRONG>The array "owns" keeps track of how much of company j =
is owned=20
by company i, whether directly or via controlled companies. The =
array=20
"controls" keeps track of which companies are controlled by which =
other=20
companies. </STRONG></P><PRE><STRONG>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define NCOM 101
int owns[NCOM][NCOM]; /* [i,j]: how much of j do i and its
controlled companies own? */
int controls[NCOM][NCOM]; /* [i, j]: does i control j? */
/* update info: now i controls j */
void
addcontroller(int i, int j)
{
int k;
if(controls[i][j]) /* already knew that */
return;
controls[i][j] =3D 1;
/* now that i controls j, add to i's holdings everything from j */
for(k=3D0; k<NCOM; k++)
owns[i][k] +=3D owns[j][k];
/* record the fact that controllers of i now control j */
for(k=3D0; k<NCOM; k++)
if(controls[k][i])
addcontroller(k, j);
/* if i now controls more companies, record that fact */
for(k=3D0; k<NCOM; k++)
if(owns[i][k] > 50)
addcontroller(i, k);
}
/* update info: i owns p% of j */
void
addowner(int i, int j, int p)
{
int k;
/* add p% of j to each controller of i */
for(k=3D0; k<NCOM; k++)
if(controls[k][i])
owns[k][j] +=3D p;
/* look for new controllers of j */
for(k=3D0; k<NCOM; k++)
if(owns[k][j] > 50)
addcontroller(k, j);
}
void
main(void)
{
FILE *fin, *fout;
int i, j, n, a, b, p;
fin =3D fopen("concom.in", "r");
fout =3D fopen("concom.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
for(i=3D0; i<NCOM; i++)
controls[i][i] =3D 1;
fscanf(fin, "%d", &n);
for(i=3D0; i<n; i++) {
fscanf(fin, "%d %d %d", &a, &b, &p);
addowner(a, b, p);
}
for(i=3D0; i<NCOM; i++)
for(j=3D0; j<NCOM; j++)
if(i !=3D j && controls[i][j])
fprintf(fout, "%d %d\n", i, j);
exit(0);
}</STRONG></PRE>
<P></P>
<HR>
</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
href=3D"http://hi.baidu.com/leokan/modify/blog/bb434e16a4252c4e20a4e9a0">=
=B1=E0=BC=AD</A> |=20
<A onclick=3D"return blogdel('blogdelform')"=20
href=3D"http://hi.baidu.com/leokan/blog/item/bb434e16a4252c4e20a4e9a0.htm=
l#">=C9=BE=B3=FD</A>=20
<FORM id=3Dblogdelform style=3D"DISPLAY: none" name=3Dblogdelform=20
action=3D/leokan/commit method=3Dpost><INPUT type=3Dhidden value=3D1 =
name=3Dct><INPUT=20
type=3Dhidden value=3D3 name=3Dcm><INPUT type=3Dhidden =
value=3Dbb434e16a4252c4e20a4e9a0=20
name=3DspBlogID><INPUT type=3Dhidden =
value=3Dhttp://hi.baidu.com/leokan/blog=20
name=3DspRefURL></FORM>
<SCRIPT language=3Djavascript>
<!--
function blogdel(str)
{
var pop=3Dnew Popup({ =
contentType:3,isReloadOnClose:false,width:340,height:80});
pop.setContent("title","=C9=BE=B3=FD=CE=C4=D5=C2");
=
pop.setContent("confirmCon","=C4=FA=C8=B7=B6=A8=D2=AA=B3=B9=B5=D7=C9=BE=B3=
=FD=D5=E2=C6=AA=CE=C4=D5=C2=BC=B0=C6=E4=CB=F9=D3=D0=C6=C0=C2=DB=C2=F0=A3=BF=
");
pop.setContent("callBack",delCallback);
pop.setContent("parameter",{fid:str,popup:pop});
pop.build();
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -