首页 > ACM题库 > HDU-杭电 > HDU 4160-Dolls-二分图-[解题报告]HOJ
2015
05-23

HDU 4160-Dolls-二分图-[解题报告]HOJ

Dolls

问题描述 :

Do you remember the box of Matryoshka dolls last week? Adam just got another box of dolls from Matryona. This time, the dolls have different shapes and sizes: some are skinny, some are fat, and some look as though they were attened. Specifically, doll i can be represented by three numbers wi, li, and hi, denoting its width, length, and height. Doll i can fit inside another doll j if and only if wi < wj , li < lj , and hi < hj .
That is, the dolls cannot be rotated when fitting one inside another. Of course, each doll may contain at most one doll right inside it. Your goal is to fit dolls inside each other so that you minimize the number of outermost dolls.

输入:

The input consists of multiple test cases. Each test case begins with a line with a single integer N, 1 ≤ N ≤ 500, denoting the number of Matryoshka dolls. Then follow N lines, each with three space-separated integers wi, li, and hi (1 ≤ wi; li; hi ≤ 10,000) denoting the size of the ith doll. Input is followed by a single line with N = 0, which should not be processed.

输出:

The input consists of multiple test cases. Each test case begins with a line with a single integer N, 1 ≤ N ≤ 500, denoting the number of Matryoshka dolls. Then follow N lines, each with three space-separated integers wi, li, and hi (1 ≤ wi; li; hi ≤ 10,000) denoting the size of the ith doll. Input is followed by a single line with N = 0, which should not be processed.

样例输入:

3
5 4 8
27 10 10
100 32 523
3
1 2 1
2 1 1
1 1 2
4
1 1 1
2 3 2
3 2 2
4 4 4
0

样例输出:

1
3
2

http://acm.hdu.edu.cn/showproblem.php?pid=4160

刚开始理解为贪心,结果题意弄错,用二分图解,一个娃娃至多装一个娃娃。

#include<stdio.h>
#include<string.h>
#include<algorithm>
struct ac
{
	int x,y,z;
}a[505];
bool map[505][505];
bool visit[505];
int path[505];
int n;
bool cmp(ac b,ac c)
{
	if(b.x<c.x) return true;
	if(b.x==c.x&&b.y<c.y) return true;
	if(b.x==c.x&&b.y==c.y&&b.z<c.z) return true;
	return false;
}
bool dfs(int x)
{
	int i;
	for(i=1;i<=n;i++)
	{
		if(map[x][i]&&!visit[i])
		{
			visit[i]=1;
			if(!path[i]||dfs(path[i]))
			{
				path[i]=x;
				return true;
			}
		}
	}
	return false;
}
void match()
{
    memset(path,0,sizeof(path));
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        memset(visit,0,sizeof(visit));
        if(dfs(i)) sum++;
    }
    printf("%d\n",n-sum);
}
int main()
{
	int i,j;
	while(scanf("%d",&n)&&n)
	{
		for(i=1;i<=n;i++)
			scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
		std::sort(a+1,a+n+1,cmp);
		memset(map,0,sizeof(map));
		for(i=1;i<n;i++)
			for(j=i+1;j<=n;j++)
				if(a[i].x<a[j].x&&a[i].y<a[j].y&&a[i].z<a[j].z)
					map[i][j]=1;
        match();
    }
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/chl_3205/article/details/7818532