http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2333
题目大意:(如题)
输入输出:(如题)
解题思路:
1.首先,确定a公司控制b公司的条件:
    (1)a公司=b公司;
    (2)a公司拥有b公司大于50%的股票
    (3)a公司控制控制的c1,c2……ck公司,每个公司拥有b公司xi%的股票,如果x1+x2+……+xk>50%
2.建立数组graph[i][j]来表示i公司拥有j公司的股份(直接/间接),isvis[i][j]表示i公司已经控制j公司。
3.每次输入公司i,j的时候对i,j和i,j相关的公司的graph和isvis进行更新。最后用两层for循环,将isvis为真的公司对输出即可。
核心代码:

void setvis(int a,int b) 
{ 
    int mi; 
    if(isvis[a][b]==true)//如果已经设置了 
        return; 
    isvis[a][b]=true;//设置控制 
    for(mi=0;mi<101;mi++) 
        graph[a][mi]+=graph[b][mi];//把b公司控制的mi公司的股份加到a公司 
    for(mi=0;mi<101;mi++) 
        if(isvis[mi][a]==true)//如果mi公司控制了a公司 
            setvis(mi,b); 
    for(mi=0;mi<101;mi++) 
        if(graph[a][mi]>50)//如果i公司控制mi公司股份超过50 
            setvis(a,mi); 
} 

发表评论

电子邮件地址不会被公开。

Post Navigation