n着色问题(pku1083).cpp

经典的着色问题

#include<iostream>
#include<queue>
using namespace std;
queue<int>Q;
int n,min;
bool flag[201];
int color[201];
int list[201][2];
int temp[201];
bool mat[201][201];
void BFS(int k)
{
	flag[k]=1;
	int i;
	memset(temp,0,sizeof(temp));
	for(i=0;i<n;i++)
	{
		if(mat[k][i]&&color[i])
		{
			temp[color[i]]=1;
		}
	}
	for(i=1;i<=n;i++)
		if(!temp[i])
		{
			color[k]=i;
			if(i>min)
				min=i;
			break;
		}
	for(i=0;i<n;i++)
	{
		if(mat[k][i]&&!flag[i])
		{
			Q.push(i);
			flag[i]=1;
		}
	}
	while(!Q.empty())
	{
		int t=Q.front();
		Q.pop();
		BFS(t);
	}
}
void solve()
{
	int i,j;
	for(i=0;i<n;i++)
	{
		for(j=0;j<i;j++)
		{
	//		if((list[i][0]%2==0)&&list[i][0]>list[j][1]+1||(list[j][0]%2==0)&&list[j][0]>list[i][1]+1)
	//			continue;
	//		if((list[i][0]%2==1)&&list[i][0]>list[j][1]||(list[j][0]%2==1)&&list[j][0]>list[i][1])
	//			continue;
			if(list[i][0]>list[j][1]||list[j][0]>list[i][1])
				continue;
			else
				mat[i][j]=mat[j][i]=1;
		}
	}
	color[0]=1;
	flag[0]=1;
	BFS(0);
	for(i=1;i<n;i++)
		if(!flag[i])
			BFS(i);
}
void ini()
{
	memset(flag,0,sizeof(flag));
	min=0;
	memset(mat,0,sizeof(mat));
	memset(color,0,sizeof(color));
}
int main()
{
	int i,j,t,a,b;
	cin>>t;
	for(i=0;i<t;i++)
	{
		ini();
		cin>>n;
		for(j=0;j<n;j++)
		{
			cin>>a>>b;
			if(a%2==1)a++;
			if(b%2==1)b++;
			list[j][0]=(a>b)?b:a;
			list[j][1]=(a>b)?a:b;
		}
		solve();
		cout<<(min)*10<<endl;
	}
	return 0;
}