HDU 4160 Dolls（二分图匹配+匈牙利算法+最小路径覆盖）

ゞ浴缸里的玫瑰 2022-06-10 02:20 217阅读 0赞

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.

Input

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.

Output

For each test case, print out a single line with an integer denoting the minimum number of outermost dolls that can be obtained by optimally nesting the given dolls.

Sample Input

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

Sample Output

1
    3
    2

题解：

题意：

给一堆娃娃和娃娃的长宽高，如果一个娃娃长宽高都小于另一个娃娃的，就可以套上去，问最少剩下多少娃娃

思路：

匈牙利算法模板题，看到数据比较小直接邻接矩阵搞的，花了200ms，看到别人用预处理一遍+邻接表搞的60ms。。看来以后有必要优化一下算法了

还有就是：最小路径覆盖=顶点数-最大匹配数

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    #define ll long long
    using namespace std;
    struct node
    {
        int len,wid,h;
    }doll[505];//存娃娃情况
    int vis[505];
    int used[505];//存套在里面的娃娃
    int n;
    int find(int u)//匈牙利算法
    {
        int i;
        for(i=1;i<=n;i++)
        {
            if(!vis[i]&&doll[i].len<doll[u].len&&doll[i].h<doll[u].h&&doll[i].wid<doll[u].wid)//没被选并且符合条件
            {
                vis[i]=1;
                if(!used[i]||find(used[i]))//如果没被套或者可以选过一个被套
                {
                    used[i]=u;
                    return 1;
                }
            }
        }
        return 0;
    }
    int main()
    {
        int i,j,k,ans;
        while(scanf("%d",&n)!=EOF&&n)
        {
            for(i=1;i<=n;i++)
            {
                used[i]=0;
                scanf("%d%d%d",&doll[i].len,&doll[i].wid,&doll[i].h);
            }
            ans=0;
            for(i=1;i<=n;i++)
            {
                memset(vis,0,sizeof(vis));
                if(find(i))
                    ans++;
            }
            printf("%d\n",n-ans);//最小路径覆盖=顶点数-最大匹配数
        }
        return 0;
    }