http://acm.hdu.edu.cn/showproblem.php?pid=3974
题目大意:
一个公司有N个员工,对于每个员工,如果他们有下属,那么他们下属的下属也是他的下属。
公司会给员工安排任务,分配给一个员工后,他也会把这个任务分配给下属。被分配到任务的人立刻停止 当前在做的工作,接受新的任务。
对于给定的M个操作
C x 输出编号为x的任务
T x y 分配任务y给x
思路:
并查集的实现,分配我们只记录在上司结点里,只不过查询的时候要把它的所有上司全部找一遍。
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=50001;
int fa[MAXN];
int val[MAXN];
int time[MAXN];
int main()
{
int T;
scanf("%d",&T);
for(int ri=1;ri<=T;ri++)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
fa[i]=i;
val[i]=-1;
time[i]=-1;
}
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
fa[a]=b;
}
printf("Case #%d:\n",ri);
int m,cnt=0;
scanf("%d",&m);
char cmd;
while(m--)
{
cin>>cmd;
if(cmd=='C')
{
int x;
scanf("%d",&x);
int cur=x,ans=val[cur],lastt=-1;
while(cur != fa[cur])
{
if(time[cur] > lastt)//后加入的
{
lastt=time[cur];
ans=val[cur];
}
cur=fa[cur];
}
if(time[cur] > lastt)//后加入的
{
lastt=time[cur];
ans=val[cur];
}
printf("%d\n",ans);
}
else
{
int x,y;
scanf("%d%d",&x,&y);
val[x]=y;
time[x]=cnt++;
}
}
}
return 0;
}
分享到:
相关推荐
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
使用并查集+贪心:先将已有边的权值从大到小排序,又n个点只需n-1条边,这时再遍历一遍,将有边的两点合并为一个队伍,当边的数量达到n-1时退出循环,因为此时已达到最小生成树。 边的权值由大到小排序是因为要将大...
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 ...并查集
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
FF is a bad boy, he is always wooing TT to play the following game with him. This is a very humdrum game. To begin with, TT should write down a sequence of integers-_-!!(bored). Then, FF can choose a ...
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu ACM 高级程序设计习题集——全文 里面有程序的详细解释
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
经典算法:(二分匹配,背包专题,筛选法,简单数学题,贪心算法,递推求解,动态规划,并查集,母函数,搜索,组合博弈等入门算法)