HDU 3974 Assign the task 并查集

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;

}

巴特西

HDU 3974 Assign the task 并查集

最新文章

热门文章