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
#include<cstdio>
#include<cstring>
using namespace std;
int father[],vis[][],num[];
void jjc(int x)
{ for (int i=;i<=x;i++)
{
father[i]=i;
num[i]=;
}
}
int find(int x)
{
while (x!=father[x])
x=father[x];
return father[x];
}
int main()
{
int n,m,k,ans,i,j,x,y,sx,sy,q;
while (~scanf("%d %d",&n,&q))
{
m=n-;
memset(vis,,sizeof(vis));
jjc(n);
while (m--)
{
scanf("%d %d",&x,&y);
sx=find(x);
sy=find(y);
if (sx!=sy)
father[sy]=sx; //不能反了
vis[x][y]=;
}
for (k=;k<=n;k++)
{
for (i=;i<=n;i++)
{
for (j=;j<=n;j++)
if (vis[i][k]==&&vis[k][j]==)
vis[i][j]=;
}
}
for (i=;i<=n;i++)
{
for (j=;j<=n;j++)
{
if (father[i]==father[j]&&i!=j&&vis[i][j]==)
num[i]++;
}
}
ans=;
for (i=;i<=n;i++)
{
if (num[i]==q)
ans++;
}
printf("%d\n",ans);
}
return ;
}
还有就是利用搜索的思想递归,放到一个矩阵里面,从第一行开始找代表找1管理的人,找到2,然后在从第二行开始找,代表找2管理的人,同时这个人也是1管理的人,找到了3,再从3开始找...
code
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int mapp[][];
int n,ans;
void bfs(int x,int y)
{
int j=y;
while (j<=n)
{
j++;
if (mapp[x][j]==)
{
ans++;
bfs(j,j);
}
}
j=y;
while (j>=)
{
j--;
if (mapp[x][j]==)
{
ans++;
bfs(j,j);
}
}
}
int main()
{
int m,k,sum,i,x,y,q;
while (~scanf("%d %d",&n,&k))
{
m=n-;sum=;
memset(mapp,,sizeof(mapp));
while (m--)
{
scanf("%d %d",&x,&y);
mapp[x][y]=;
}
for (i=;i<=n;i++)
{
ans=;
bfs(i,i);
// printf("%d\n",ans);
if (ans==k)
sum++;
}
printf("%d\n",sum);
}
return ;
}