题目链接：

题目

Problem 1014 xxx游戏

Time Limit: 1000 mSec

Memory Limit : 32768 KB

问题描述

小M最近很喜欢玩XXX游戏。这个游戏很简单，仅由3个场景（分别为1、2、3）构成构成，只存在1->2、2->3、3->1的路径，三条路径的时间花费都是1个小时。

由于剧情需要，这个游戏有N个剧情任务，每个剧情任务在其中一个场景中完成，但是某些剧情的触发前提是一些必要剧情任务已经完成。为了简化问题，每个剧情任务都只需要一个小时就可以完成。

小M想要花最少的时间通关，然而他还有很多考试，所以请你计算出通关所需要的最少时间。

一开始，你可以选择1、2、3其中一个场景开始做任务。

输入

第一行为整数T(T<=20)，表示测试数据组数。

每组数据的第一行为整数N(N<=200)，表示剧情数。

第二行包含N个整数Ci(1<=Ci<=3)，表示第i个剧情需要在场景Ci中完成。

接下来N行，每行包含一个整数t(0<=t<=N-1)，表示做剧情任务i前需要先完成t个剧情任务。然后是t个不同的整数Aij(1<=Aij<=N),表示剧情编号。

题目保证不会出现相互依赖的情况，即不出现环。

输出

最少时间数。

样例

input

2

1

1

0

5

2 2 1 1 3

1 5

2 5 1

2 5 4

1 5

0

output

1

7

题解

每个场景开一个队列保存入度为0的点，枚举开始的场景，然后拓扑排序模拟，贪心把当前场景能完成的任务都完成。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

#include<map>

#include<queue>

using namespace std;

typedef __int64 LL;

const int maxn=222;

const LL INF=0x3f3f3f3f3f3f3f3fLL;

vector<int> arr[3],G[maxn];

queue<int> Q[3];

int in[maxn],id[maxn],used[maxn];

int n;

int inn[maxn];

LL solve(int st){

	LL ret=0,cnt=0;

	for(int i=0;i<maxn;i++) inn[i]=in[i];

	for(int i=0;i<3;i++){

		while(!Q[i].empty()) Q[i].pop();

	}

	for(int now=0;now<3;now++){

		for(int i=0;i<arr[now].size();i++){

			int v=arr[now][i];

			if(inn[v]==0) Q[now].push(v);

		}

	}

	for(int now=st;;now=(now+1)%3){

		while(!Q[now].empty()){

			int u=Q[now].front(); Q[now].pop();

			ret++; cnt++;

			for(int i=0;i<G[u].size();i++){

				int v=G[u][i];

				inn[v]--;

				if(inn[v]==0) Q[id[v]].push(v);

			}

		}

		if(Q[0].empty()&&Q[1].empty()&&Q[2].empty()) break;

		ret++;

	}

	return ret;

}

void init(){

	memset(in,0,sizeof(in));

	for(int i=0;i<maxn;i++) G[i].clear();

	for(int i=0;i<3;i++) arr[i].clear();

}

int main(){

	int tc;

	scanf("%d",&tc);

	while(tc--){

		init();

		scanf("%d",&n);

		for(int i=0;i<n;i++){

			int x; scanf("%d",&x),x--;

			arr[x].push_back(i);

			id[i]=x;

		}

		for(int i=0;i<n;i++){

			int cnt; scanf("%d",&cnt);

			while(cnt--){

				int x; scanf("%d",&x),x--;

				G[x].push_back(i);

				in[i]++;

			}

		}

		LL ans=INF;

		for(int i=0;i<3;i++){

			ans=min(ans,solve(i));

		}

		printf("%I64d\n",ans);

	}

	return 0;

}