Controlling Companies?控制公司
有些公司是其他公司的部分擁有者,因為他們獲得了其他公司發行的股票的一部分.例如,福特公司
擁有馬自達公司 12%的股票.據說,如果至少滿足了以下條件之一,公司 A 就可以控制公司 B 了:
公司 A = 公司 B.
公司 A 擁有大于 50%的公司 B 的股票.
公司A控制K(K >= 1)個公司,記為C1, ..., CK,每個公司Ci擁有xi%的公司B的股票,并且x1+ ....
+ xK > 50%.
你將被給予一系列的三對數（i,j,p）,表明公司 i 享有公司 j 的 p%的股票.計算所有的數對（h,s）,
表明公司 h 控制公司 s.至多有 100 個公司.
寫一個程序讀入三對數（i,j,p）,i,j和p是都在范圍(1..100)的正整數,并且找出所有的數對（h,s）,
使得公司 h 控制公司 s.
PROGRAM NAME: concom
INPUT FORMAT
第一行: N,表明接下來三對數的數量.
第二行到第 N+1 行: 每行三個整數作為一個三對數（i,j,p）,如上文所述.
SAMPLE INPUT (file concom.in)
3
1 2 80
2 3 80
3 1 20
OUTPUT FORMAT
輸出零個或更多個的控制其他公司的公司.每行包括兩個整數表明序號為第一個整數的公司控制了
序號為第二個整數的公司.將輸出的每行以第一個數字升序排列（并且第二個數字也升序排列來避
免并列）.請不要輸出控制自己的公司.
SAMPLE OUTPUT (file concom.out)
1 2
1 3

2 3

看得懂題解但自己寫不出來思路不夠清晰

/*
ID:jinbo wu
LANG:C++
TASK:concom
*/
#include<bits/stdc++.h>
using namespace std;
int a[105][105];
int b[105][105];
int n,maxn;
void dfs(int i,int j)
{for(int k=1;k<=maxn;k++){if(k!=i&&b[i][k]<=50){b[i][k]+=a[j][k];if(b[i][k]>50)dfs(i,k);}}}
int main()
{freopen("concom.in","r",stdin);freopen("concom.out","w",stdout);cin>>n;int x,y,z;for(int i=0;i<n;i++){cin>>x>>y>>z;a[x][y]=z;maxn=max(maxn,max(x,y));}
memcpy(b,a,sizeof(a));
for(int i=1;i<=maxn;i++)
{for(int j=1;j<=maxn;j++){if(i!=j&&a[i][j]>50)dfs(i,j);}
}
for(int i=1;i<=maxn;i++)
for(int j=1;j<=maxn;j++)
{if(i!=j&&b[i][j]>50)cout<<i<<" "<<j<<endl;
}
}

總結

以上是生活随笔為你收集整理的usaco Controlling Companies的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。