2419577_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <algorithm>
using namespace std;
int r;
int map[13][9], h[13][9];
int b[9], link[9];
struct node
{
	int id;
	int st, ed;
}peo[13];

bool cmp(struct node a,struct node b)
{
	if(a.st!=b.st)
		return a.st<b.st;
	else
		return a.ed<b.ed;
}

int find(int v)
{
	int i;

	for(i = 1; i <= 8; i++)
	{
		if(map[v][i]&&!b[i])
		{
			b[i] = 1;
			if(link[i]==0||find(link[i]))
			{
				link[i] = v;
				return 1;
			}
		}
	}
	return 0;
}

void solve()
{
	int i, j, k;

	for(i = 1; i <= r; i++)
	{
		for(j = 1; j <= h[peo[i].id][0]; j++)
			map[i][h[peo[i].id][j]] = 1;
	}
	for(i = 1; i <= r; i++)
	{
		memset(b,0,sizeof(b));
		for(j = 1; j < i; j++)
		{
			if(peo[j].ed<peo[i].st)
			{
				for(k = 1; k <= 8; k++)
				{
					if(link[k]==j)
						link[k] = 0;
				}
			}
		}
		if(!find(i))
		{
			printf("NO\n");
			return ;
		}
	}
	printf("YES\n");
}

int main()
{
	int t, i, k, j;

	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&r);
		memset(link,0,sizeof(link));
		for(i = 1; i <= r; i++)
		{
			scanf("%d%d",&peo[i].st,&peo[i].ed);
			peo[i].id = i;
			scanf("%d",&k);
			h[i][0] = k;
			for(j = 0; j < k; j++)
				scanf("%d",&h[i][j+1]);
		}
		sort(peo,peo+r,cmp);
		solve();
	}
	return 1;
}