P1475 [USACO2.3] 控制公司 Controlling Companies

题目描述

有些公司是其他公司的部分拥有者，因为他们获得了其他公司发行的股票的一部分。

据说，如果至少满足了以下三个条件之一，公司 $A$ 就可以控制公司 $B$ 了：

• 公司 $A$ = 公司 $B$。
• 公司 $A$ 拥有大于 $50\%$ 的公司 $B$ 的股票。
• 公司 $A$ 控制 $K$（$K\ge 1$）个公司，记为 $C_1,\dots ,C_K$，每个公司 $C_i$ 拥有 $x_i\%$ 的公司 $B$ 的股票，并且 $x_1+\dots +x_K>50\%$。

给你一个表，每行包括三个数 $i,j,p$：表明公司 $i$ 享有公司 $j$ 的 $p\%$ 的股票。计算所有的数对 $(h,s)$，表明公司 $h$ 控制公司 $s$。至多有 $100$ 个公司。

输入格式

第一行一个整数 $N$，表明表格的行数。

接下来 $N$ 行，每行三个整数 $i,j,p$，表示 $i$ 公司拥有 $j$ 公司 $p\%$ 的股份。

输出格式

输出零个或更多个的控制其他公司的公司。每行包括两个整数 $A,B$，表示 $A$ 公司控制了 $B$ 公司。将输出的数对以 $A$ 为第一关键字，$B$ 为第二关键字升序排列。

请不要输出控制自己的公司（即你输出的数对均要满足 $A\ne B$）。

输入输出样例 #1

输入 #1

3
1 2 80
2 3 80
3 1 20

输出 #1

1 2
1 3
2 3

说明/提示

翻译来自NOCOW

USACO 2.3

C++实现

#include
#include
#include
using namespace std;
int n;//表示出现公司的大小
int a[110][110],f[110];
bool v[110],c[110];
void dfs(int k){
if(v[k]==true) return;//如果搜索过了，就不用管了
v[k]=true;//改为被搜索过
for(int i=1;i<=n;i++){
f[i]+=a[k][i];
if(f[i]>50) {
c[i]=true;//记为被控制
dfs(i);//往下深搜
}
}
}
int main()
{
int i,j,x,y,z,t;
scanf(“%d”,&t);//输入
for(i=1;i<=t;i++) {
scanf(“%d%d%d”,&x,&y,&z);
a[x][y]=z;n=max(n,max(x,y));
}
for(i=1;i<=n;i++) {
memset(v,false,sizeof(v));//初始化
memset(c,false,sizeof©);
memset(f,0,sizeof(f));
dfs(i);//从第i个公司开始深搜
for(j=1;j<=n;j++)
if(c[j]==true && i!=j)//如果控制了，就输出
printf(“%d %d\n”,i,j);
}
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容