[usaco]Controlling Companies

題意：給你n個公司股份的關系，一個公司控制另一個公式的條件是這個公司擁有另一個公司50% 或以上的股份，或者這個公司控制的子公司擁有另一家公司的股份總數>=50%;

1 // File Name: concom.c
 2 // Author: darkdream
 3 // Created Time: 2013年12月11日 星期三 13時12分05秒
 4 /*
 5 ID: dream.y1
 6 PROG: concom
 7 LANG: C++
 8 */
 9 #include<stdio.h>
10 #include<string.h>
11 #include<stdlib.h>
12 #include<time.h>
13 #include<math.h>
14 int hs[200][200] = {0};
15 double map[200][200] = {0};
16 int k;
17 int visit[200] = {0};
18 void dfs()
19 {
20     for(int i = 1;i <= 100 ;i ++)
21     {
22       int ok = 0 ;
23       if(hs[k][i] && !visit[i] )
24       {
25          visit[i] = 1;
26          for(int j = 1;j <= 100 ;j ++)
27          {
28             map[k][j] += map[i][j];
29             if(map[k][j] >= 0.5)
30             {
31                hs[k][j] = 1; 
32                ok = 1;
33             }
34          }
35          
36       }
37       if(ok)
38           i = 0 ;
39     }
40 }
41 int main(){
42     freopen("concom.in","r",stdin);
43     freopen("concom.out","w",stdout);
44     int n ;
45     scanf("%d",&n);
46     for(int i = 1;i <= n;i ++)
47     {
48         int a, b ,temp;
49         scanf("%d %d %d",&a,&b,&temp);
50         map[a][b] = temp*1.0/100;
51         if(map[a][b] >=  0.5- 1e-8)
52         {
53             hs[a][b] = 1;
54         }
55     }
56     for(k =1 ;k <= 100; k ++)
57     {
58         memset(visit,0,sizeof(visit));
59         visit[k] = 1;
60         dfs();
61     }
62     for(int i = 1;i <= 100;i ++)
63         for(int j = 1; j<= 100  ;j ++)
64         {
65             if(hs[i][j] && i != j )
66                 printf("%d %d\n",i,j);
67         }
68     return 0 ;
69 }      

View Code