2801332_ac_250ms_1608k.cpp

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

#include <stdio.h>
#include <algorithm>

using namespace std;

int num;

struct node
{
	int x, y;
}pot[25*25];

int map[25*25][25*25];
int link[25*25], bb[25*25];

int dfs(int v)
{
	int i;

	for(i = 0; i < num; i++)
	{
		if(map[v][i]&&!bb[i])
		{
			bb[i] = 1;
			if(link[i]==-1||dfs(link[i]))
			{
				link[i] = v;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	int a, b;
	int i, j;
	int ans;

	while(scanf("%d%d",&a,&b)==2)
	{
		if(a==-1&&b==-1)
			break;
		num = 1;
		pot[0].x = a;pot[0].y = b;
		while(scanf("%d%d",&pot[num].x,&pot[num].y)==2,pot[num].x)
			num++;
		memset(map,0,sizeof(map));
		for(i = 0; i < num; i++)
			for(j = 0; j < num; j++)
			{
				if(i!=j&&pot[j].x<=pot[i].x&&pot[j].y<=pot[i].y)
					map[i][j] = 1;
			}
		ans = 0;
		memset(link,-1,sizeof(link));
		for(i = 0; i < num; i++)
		{
			memset(bb,0,sizeof(bb));
			ans += dfs(i);
		}
		printf("%d\n",num-ans);
	}
	return 0;
}