套盒子

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 27 Accepted Submission(s) : 4

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

盒子 i 可以用宽wi, 长li, and 高hi表示. 盒子 i 可以放在盒子 j中当前仅当 wi < wj , li < lj , and hi < hj . 我们规定每个盒子中最多只能放一个盒子., 但是允许嵌套. 即任意两个盒子不能同在一个盒子中, 但是盒子i可以在盒子j中,然后盒子j又可以在k中. 给你若干盒子,怎样套才能保证留在最外面的盒子最少?

Input

输入包含多个测试用例.每个测试用例的第一行是一个整数N, 1<=N<=500, 表示盒子的数目. 接下来有N行, 每一行都是空格隔开的三个整数wi, li, 和 hi (1 <= wi, li, hi<= 10000). 输入的最后一行是N = 0, 表示结束.

Output

对于每一测试用例,单行输出能得到的最小值

Sample Input

35 4 827 10 10100 32 52331 2 12 1 11 1 241 1 12 3 23 2 24 4 40

Sample Output

#include
   
    #include
    
     #define MAXN 505int g[MAXN][MAXN];struct Info{	int x,y,z;}info[MAXN];int linker[MAXN];bool vis[MAXN];int uN, vN;bool ok(int i, int j){	return (info[i].x > info[j].x) && (info[i].y > info[j].y) && (info[i].z > info[j].z);}bool dfs(int root){	int i;	for(i = 0; i < vN; i++)	{		if(g[root][i]&&!vis[i])		{			vis[i] = 1;			if(linker[i]==-1)			{				linker[i] = root;				return 1;			}			else			{				if(dfs(linker[i]))				{					linker[i] = root;					return 1;				}			}		}	}	return 0;}int main(){	int N, i, j, ans;	while(scanf("%d",&N) && N)	{		for(i = 0; i < N; i++)			scanf("%d%d%d", &info[i].x, &info[i].y, &info[i].z);		memset(g, 0, sizeof(g));		for(i = 0; i < N; i++)			for(j = 0; j < N; j++)			{				if(ok(i, j))					g[i][j] = 1;			}               /**匈牙利匹配算法**/                ans = uN = vN = N;//uN:左边的点，vN右边的点,ans值 （即最小覆盖点）=N - 最大匹配		memset(linker, -1, sizeof(linker));		for(i = 0; i < uN; i++)		{			memset(vis, 0, sizeof(vis));			if(dfs(i))				ans--;		}              printf("%d\n", ans);	}	return 0;}

转载地址：http://weuvi.baihongyu.com/

你可能感兴趣的文章