51nod 1392：装盒子匈牙利+贪心

基准时间限制：1 秒空间限制：131072 KB 分值: 160 难度：6级算法题

关注

有n个长方形盒子，第i个长度为Li，宽度为Wi，我们需要把他们套放。注意一个盒子只可以套入长和宽分别不小于它的盒子，并且一个盒子里最多只能直接装入另外一个盒子（但是可以不断嵌套），例如1 * 1 可以套入2 * 1，而2 * 1再套入2 * 2。套入之后盒子占地面积是最外面盒子的占地面积。给定N个盒子大小，求最终最小的总占地面积。

Input

第一行一个数N表示盒子的个数。

接下来N行，每行两个正整数，表示每个盒子的长度和宽度。

所有整数都是正的（N，以及盒子的长宽），且不超过200。

Output

一行一个整数表示最终最小的占地面积。

Input示例

Output示例

将能够装进的两个盒子连一条边，然后按照面积大小对盒子排序进行二分图的最大匹配，匹配成功了就将总的面积-装进的盒子的面积。

代码：

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#pragma warning(disable:4996)

using namespace std;

int grid[805][805];

int link[805];

int visit[805];

int n, sum2, V1, V2;

struct no {

	int x;

	int y;

}node[205];

bool cmp(const no&node1,const no&node2)

{

	return node1.x*node1.y < node2.x*node2.y;

}

bool dfs(int x)

{

	int i;

	for (i = V2; i>=1; i--)

	{

		if (grid[x][i] && visit[i] == 0)

		{

			visit[i] = 1;

			if (link[i] == -1 || dfs(link[i]))

			{

				link[i] = x;

				return true;

			}

		}

	}

	return false;

}

void Magyarors()

{

	int i;

	memset(link, -1, sizeof(link));//！！这里不能是0  

	for (i = V1; i>=1; i--)

	{

		memset(visit, 0, sizeof(visit));

		if (dfs(i))

		{

			sum2 = sum2 - node[i].x*node[i].y;

		}

	}

	cout << sum2 << endl;

}

int main()

{

	//freopen("i.txt","r",stdin);

	// freopen("o.txt","w",stdout);

	int i,j,sum=0;

	scanf("%d",&n);

	V1 = V2 = n;

	for (i = 1; i <= n; i++)

	{

		scanf("%d%d",&node[i].x,&node[i].y);

		sum2 += node[i].x*node[i].y;

	}

	sort(node + 1, node + n + 1, cmp);

	for (i = 1; i <= n; i++)

	{

		for (j = i+1; j <= n; j++)

		{

			if (node[j].x >= node[i].x&&node[j].y >= node[i].y)

			{

				grid[i][j] = 1;

			}

		}

	}

	Magyarors();

	return 0;

}

巴特西

51nod 1392：装盒子匈牙利+贪心

最新文章

热门文章

巴特西

51nod 1392：装盒子 匈牙利+贪心

最新文章

热门文章

51nod 1392：装盒子匈牙利+贪心