Dolls - 4160(简单二分图匹配)

题意:有一些箱子,大箱子可以套小箱子,但是必须h>h,w>w,l>l,求出来最外面能剩下几个箱子无法被嵌套。
 
分析:思考每个箱子都只会被别的箱子套一次,所以构成一二分匹配模型,只需求出来最大的匹配,因为没有匹配的都是无法被嵌套的,已经匹配的都可以找到嵌套它的箱子,结果就是箱子总数-最大匹配。
代码如下:
=======================================================================================================================================
#include<stdio.h>
#include<string.h> const int MAXN = ;
const int oo = 1e9+; struct point{int wi, li, hi;}p[MAXN];
int G[MAXN][MAXN], Ly[MAXN], N;
bool used[MAXN]; bool OK(point a, point b)
{
if(a.hi<b.hi && a.li<b.li && a.wi<b.wi)
return true;
return false;
}
bool Find(int i)
{
for(int j=; j<=N; j++)
{
if(!used[j] && G[i][j])
{
used[j] = true; if(!Ly[j] || Find(Ly[j]))
{
Ly[j] = i;
return true;
}
}
} return false;
}
int XYL()
{
memset(Ly, , sizeof(Ly));
int ans = ; for(int i=; i<=N; i++)
{
memset(used, false, sizeof(used));
if(Find(i) == true)
ans++;
} return ans;
} int main()
{
while(scanf("%d", &N), N)
{
int i, j; memset(G, , sizeof(G)); for(i=; i<=N; i++)
scanf("%d%d%d", &p[i].wi, &p[i].li, &p[i].hi); for(i=; i<=N; i++)
for(j=; j<=N; j++)
{
if(OK(p[i], p[j]) == true)
G[i][j] = ;
} printf("%d\n", N-XYL());
} return ;
}
上一篇:SQL Server 日期字段作为查询标志字段的注意事项


下一篇:Swap HDU - 2819 (有关矩阵的二分匹配)