题解 P1475 【控制公司 Controlling Companies】

以墨 · 2017-05-13 22:40:21 · 题解

直接用dfs

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[102][102];//a[i][j]表示公司i拥有公司j百分之a[i][j]的股份
int cnt[102]；//cnt[i]表示当前阶段中公司x拥有公司i累计有百分之cnt[i]的股份
int m;
bool f[102]；//f[i]表示当前阶段中第i个公司是否被搜索过
bool own[102];//own[i]表示当前阶段中公司x是否能控制公司i
void EMILY(int x)
{
    if(f[x]==true)//边界条件，如果当前公司已被搜索过，则直接返回
        return ;
    f[x]=true;//标记为搜索过
    for(int i=m;i;i--)//枚举所有公司
    {
        cnt[i]+=a[x][i];//加上当前公司的股份百分点
        if(cnt[i]>50)//满足条件
        {
            own[i]=true;//设置为能够控制
            EMILY(i);//递归
        }
    }
}
int main()
{
    freopen("1475.in","r",stdin);
    freopen("1475.out","w",stdout);
    int i,j,k,u,v,w,n;
    for(scanf("%d",&n);n;n--)
    {
        scanf("%d%d%d",&u,&v,&w);
        a[u][v]=w;//公司u拥有公司v百分之w的股份
        m=max(u,max(m,v));//m为公司的个数
    }
    for(i=1;i<=m;i++)
    {
        memset(f,false,sizeof(f));//把遍历情况全部清空
        memset(own,false,sizeof(own));//把所属情况全部置为false
        memset(cnt,0,sizeof(cnt));//把累计百分点全部清零
        EMILY(i);//从第i个公司开始搜索
        for(j=1;j<=m;j++)
            if(own[j]==true&&i!=j)//如果公司j属于公司i且i不等于j
                printf("%d %d\n",i,j);//输出公司i控制公司j
    }
    return 0;
}