A40945. 控制公司
填空题
困难
知识点
题目描述
控制公司
题目描述
有些公司是其他公司的部分拥有者，因为他们获得了其他公司发行的股票的一部分。例如，福特公司拥有马自达公司12%的股票。据说，如果至少满足了以下条件之一，公司A就可以控制公司B了：
l 公司A = 公司B。
l 公司A拥有大于50%的公司B的股票。
l 公司A控制K(K >= 1)个公司，记为C1, …, CK，每个公司Ci拥有xi%的公司B的股票，并且x1+ … + xK > 50%。（ps：A可以控制自己，即Ci可以为A）
你将被给予一系列的三对数（i，j，p），表明公司i拥有公司j的p%的股票。计算所有的数对（h，s），表明公司h控制公司s。
写一个程序读入三对数（i，j，p），并且找出所有的数对（h，s），使得公司h控制公司s。
输入
第一行： N，表明接下来三对数的数量。 第二行到第N+1行：每行三个整数作为一个三对数（i，j，p），如上文所述。 I，J≤100，N，P≤100
输出
输出零个或更多个的控制其他公司的公司。每行包括两个整数表明序号为第一个整数的公司控制了序号为第二个整数的公司。将输出的每行以第一个数字升序排列（并且第二个数字也升序排列来避免并列）。请不要输出控制自己的公司。
样例输入
3
1 2 80
2 3 80
3 1 20
样例输出
1 2
1 3
2 3
参考答案
#include<bits/stdc++.h>
using namespace std;
unsigned long long int n,gf[1000][1000],mp[1000][1000];
void jf(int x,int y)//x公司加上i公司股票
{
for(int i=1;i<=100;i++)
{
if(gf[x][i]+gf[y][i]>100) gf[x][i]=100;//判断
else gf[x][i]+=gf[y][i];
}
return ;
}
void find(int x)//递归
{
for(int i=1;i<=100;i++)
{
if(gf[x][i]>=50&&mp[x][i]==0&&x!=i)
{
mp[x][i]=1;//标记 x公司可以控制i公司
jf(x,i);
find(x);//加上以后再找一遍
return ;
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;
gf[a][b]=c;
}
int t=1;
while(t<=100)//枚举每一个公司
{
find(t);
t++;
}
for(int i=1;i<=100;i++)
{
for(int j=1;j<=100;j++)
{
if(mp[i][j]==1) cout<<i<<" "<<j<<endl;
}
}
}
上一题
下一题