ydc的博客

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 60
#define MAXM 3600
#define x first
#define y second
using namespace std;
struct Box
{
	int n,m,out[MAXN],p[MAXN][2];
	bool flag[MAXN];
	void Read()
	{
		scanf("%d %d",&n,&m);
		for(int i=1;i<=m;i++)
		{
			scanf("%d",&out[i]);
			flag[++out[i]]=true;
		}
		for(int i=1;i<=n;i++)
		{
			scanf("%d %d",&p[i][0],&p[i][1]);
			p[i][0]++,p[i][1]++;
		}
	}
	friend bool operator < (const Box &a,const Box &b)
	{
		static pair<int,int> queue[MAXM],head;
		static bool use[MAXN][MAXN];
		for(int i=1;i<=a.n;i++)
			for(int j=1;j<=b.n;j++)
				use[i][j]=false;
		int front=0,rear=1;
		queue[rear]=make_pair(1,1);
		use[1][1]=true;
		while(front<rear)
		{
			head=queue[++front];
			if(a.flag[head.x]&&!b.flag[head.y])  return false;
			for(int i=0;i<=1;i++)
			{
				int x=a.p[head.x][i],y=b.p[head.y][i];
				if(use[x][y])  continue;
				use[x][y]=true,queue[++rear]=make_pair(x,y);
			}
		}
		return true;
	}
}pandora[MAXN];
bool use[MAXN];
int n;
int tot,to[MAXM],next[MAXM],start[MAXN];
void make(int a,int b){  tot++,to[tot]=b,next[tot]=start[a],start[a]=tot;  }
void read()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		pandora[i].Read();
}
void Make_Graph()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i!=j&&pandora[i]<pandora[j])
				make(i,j);
}
bool DFS(int p,int dep,int n)
{
	if(dep>n)  return true;
	use[p]=true;
	for(int i=start[p];i;i=next[i])
		if(use[to[i]]==false&&DFS(to[i],dep+1,n))
		{
			use[p]=false;
			return true;
		}
	use[p]=false;
	return false;
}
int Longest_Path()
{
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		bool mark=false;
		for(int j=1;j<=n&&mark==false;j++)
			if(DFS(j,2,i))
				mark=true;
		if(mark==false)  break;
		ans=i;
	}
	return ans;
}
int main()
{
	read();
	Make_Graph();
	printf("%d\n",Longest_Path());
	return 0;
}