hdu 5326(基础题) work

http://acm.hdu.edu.cn/showproblem.php?pid=5326

一道水题,题目大意是在公司里,给出n个员工和目标人数m,然后下面的n-1行是表示员工a管理b,问在这些员工中有多少管理员工的人数是k

起初想的是并查集,后来发现没那么简单,因为两者之间的关系有方向的,a管理b是单向的从b指到a,所以并查集的一个集合里包含了很多种关系

还需要用一个二维数组表示关系,它是一环扣一环的从a找到b再从b找到c......因为如果b管理c,a又管理b,那么a也管理c

code

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int father[101],vis[101][101],num[101];
 5 void jjc(int x)
 6 {
 7 
 8     for (int i=1;i<=x;i++)
 9     {
10        father[i]=i;
11        num[i]=0;
12     }
13 }
14 int find(int x)
15 {
16     while (x!=father[x])
17        x=father[x];
18     return father[x];
19 }
20 int main()
21 {
22     int n,m,k,ans,i,j,x,y,sx,sy,q;
23     while (~scanf("%d %d",&n,&q))
24     {
25         m=n-1;
26         memset(vis,0,sizeof(vis));
27         jjc(n);
28         while (m--)
29         {
30             scanf("%d %d",&x,&y);
31             sx=find(x);
32             sy=find(y);
33             if (sx!=sy)
34                father[sy]=sx; //不能反了
35             vis[x][y]=1;
36         }
37         for (k=1;k<=n;k++)
38         {
39             for (i=1;i<=n;i++)
40             {
41                 for (j=1;j<=n;j++)
42                 if (vis[i][k]==1&&vis[k][j]==1)
43                     vis[i][j]=1;
44             }
45         }
46         for (i=1;i<=n;i++)
47         {
48             for (j=1;j<=n;j++)
49             {
50                 if (father[i]==father[j]&&i!=j&&vis[i][j]==1)
51                    num[i]++;
52             }
53         }
54         ans=0;
55         for (i=1;i<=n;i++)
56         {
57            if (num[i]==q)
58               ans++;
59         }
60         printf("%d
",ans);
61     }
62     return 0;
63 }

还有就是利用搜索的思想递归,放到一个矩阵里面,从第一行开始找代表找1管理的人,找到2,然后在从第二行开始找,代表找2管理的人,同时这个人也是1管理的人,找到了3,再从3开始找...

code

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int mapp[101][101];
int n,ans;
void bfs(int x,int y)
{
    int j=y;
    while (j<=n)
    {
        j++;
        if (mapp[x][j]==0)
        {
            ans++;
            bfs(j,j);
        }
    }
    j=y;
    while (j>=1)
    {
        j--;
        if (mapp[x][j]==0)
        {
            ans++;
            bfs(j,j);
        }
    }
}
int main()
{
    int m,k,sum,i,x,y,q;
    while (~scanf("%d %d",&n,&k))
    {
        m=n-1;sum=0;
        memset(mapp,1,sizeof(mapp));
        while (m--)
        {
            scanf("%d %d",&x,&y);
            mapp[x][y]=0;
        }
        for (i=1;i<=n;i++)
        {
            ans=0;
            bfs(i,i);
           // printf("%d
",ans);
            if (ans==k)
               sum++;
        }
       printf("%d
",sum);
    }
    return 0;
}