收藏
关注
有n个长方形盒子，第i个长度为Li，宽度为Wi，我们需要把他们套放。注意一个盒子只可以套入长和宽分别不小于它的盒子，并且一个盒子里最多只能直接装入另外一个盒子 （但是可以不断嵌套），例如1 * 1 可以套入2 * 1，而2 * 1再套入2 * 2。套入之后盒子占地面积是最外面盒子的占地面积。给定N个盒子大小，求最终最小的总占地面积。
Input
第一行一个数N表示盒子的个数。 接下来N行，每行两个正整数，表示每个盒子的长度和宽度。 所有整数都是正的（N，以及盒子的长宽），且不超过200。
Output
一行一个整数表示最终最小的占地面积。
Input示例
3 1 1 1 2 2 1
Output示例
4
将能够装进的两个盒子连一条边，然后按照面积大小对盒子排序进行二分图的最大匹配，匹配成功了就将总的面积-装进的盒子的面积。
代码：
#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;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。