记录编号	249214	评测结果	AAAAAAAAAA
题目名称	[HNOI 2006]潘多拉的宝盒	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.095 s
提交时间	2016-04-12 13:05:08	内存使用	13.74 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>
using namespace std;
const int maxs=51;
const int maxn=51;
int G[maxs][maxn][2];
int P[maxs][maxn],S,n,m;
bool vis[maxn][maxn];
int cnt,fir[maxs],nxt[maxs*maxs*2],to[maxs*maxs*2];
void addedge(int a,int b){
	nxt[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;
}
struct Node{
	int x,y;
};
queue<Node>q;
void Solve(int x,int y){
	bool a=true,b=true;
	memset(vis,false,sizeof(vis));
	q.push((Node){0,0});vis[0][0]=true;
	while(!q.empty()){
		Node p=q.front();q.pop();
		if(P[x][p.x]^P[y][p.y]){
			if(P[x][p.x])b=false;
			if(P[y][p.y])a=false;	
		}
		if(!vis[G[x][p.x][0]][G[y][p.y][0]]){
			vis[G[x][p.x][0]][G[y][p.y][0]]=true;
			q.push((Node){G[x][p.x][0],G[y][p.y][0]});
		}
		if(!vis[G[x][p.x][1]][G[y][p.y][1]]){
			vis[G[x][p.x][1]][G[y][p.y][1]]=true;
			q.push((Node){G[x][p.x][1],G[y][p.y][1]});
		}
	}
	if(a)addedge(y,x);
	if(b)addedge(x,y);
	return;	
}
int ID[maxs],low[maxs],tot;
int cntot,ring[maxs],val[maxs],inst[maxs];
stack<int>st;
void Tarjan(int x){
	ID[x]=low[x]=++tot;inst[x]=true;st.push(x);
	for(int i=fir[x];i;i=nxt[i]){
		if(ID[to[i]]){
			if(inst[to[i]])	
				low[x]=min(low[x],ID[to[i]]);
		}
		else{
			Tarjan(to[i]);
			low[x]=min(low[x],low[to[i]]);
		}
	}
	if(ID[x]==low[x]){
		while(true){
			int y=st.top();st.pop();inst[y]=false;
			ring[y]=cntot;val[cntot]++;
			if(y==x)break;
		}
		++cntot;
	}
}
int ans,ansd;
bool E[maxs][maxs];
int path[maxs],ret[maxs];
void DFS(int x,int v,int dep){
	bool flag=false;path[dep]=x;
	for(int i=0;i<cntot;i++)
		if(E[x][i]){
			flag=true;
			DFS(i,v+val[i],dep+1);
		}
	if(!flag&&v>=ans){
		ans=v;ansd=dep;
		memcpy(ret,path,sizeof(ret));
	}
	return;
}
int main(){
	freopen("pandora.in","r",stdin);
	freopen("pandora.out","w",stdout);
	scanf("%d",&S);
	for(int k=0;k<S;k++){
		scanf("%d%d",&n,&m);
		for(int i=0,x;i<m;i++){
			scanf("%d",&x);	
			P[k][x]=true;
		}
		for(int i=0;i<n;i++)
			scanf("%d%d",&G[k][i][0],&G[k][i][1]);	
	}
	for(int i=0;i<S;i++)
		for(int j=i+1;j<S;j++)
			Solve(i,j);
	
	for(int i=0;i<S;i++)
		if(!ID[i])
			Tarjan(i);
	
	for(int x=0;x<S;x++)
		for(int i=fir[x];i;i=nxt[i])
			if(ring[to[i]]!=ring[x])
				E[ring[x]][ring[to[i]]]=true;	

	for(int i=0;i<cntot;i++)		
		DFS(i,val[i],1);
	printf("%d\n ",ans);bool flag=0;
	for(int i=1;i<=ansd;i++){
		for(int j=0;j<S;j++)
		if(ring[j]==ret[i]){
			if(flag)
				printf(" %d",j);
			else
				printf("%d",j);
			flag=true;	
		}
	}
	printf("\n");
}