比赛 20121009 评测结果 WWWWW
题目名称 木棍 最终得分 0
用户昵称 Truth.Cirno 运行时间 0.693 s
代码语言 C++ 内存使用 98.40 MiB
提交时间 2012-10-09 21:22:15
显示代码纯文本
#include <iostream>
#include <cstdio>
using namespace std;

int l[5010],w[5010],waynum[5010],wayto[5010][5010],innum[5010];
bool used[5010];

int main(void)
{
	freopen("wooden.in","r",stdin);
	freopen("wooden.out","w",stdout);
	int i,j,n,rest,minnum,minpos,pos,to,c=0;
	cin>>n;
	rest=n;
	for (i=1;i<=n;i++)
		cin>>l[i]>>w[i];
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		{
			if (i==j)
				continue;
			if (l[i]<=l[j]&&w[i]<=w[j])
			{
				waynum[i]++;
				wayto[i][waynum[i]]=j;
				innum[j]++;
			}
		}
	while (rest)
	{
		c++;
		minnum=10000;
		for (i=1;i<=n;i++)
			if (!used[i]&&minnum>innum[i])
			{
				minnum=innum[i];
				minpos=i;
			}
		while (minnum!=10000)
		{
			minnum=10000;
			pos=minpos;
			used[pos]=true;
			rest--;
			for (i=1;i<=waynum[pos];i++)
			{
				to=wayto[pos][i];
				innum[to]--;
				if (!used[to]&&minnum>innum[to])
				{
					minnum=innum[to];
					minpos=to;
				}
			}
		}
	}
	cout<<c<<endl;
	return(0);
}