POJ 2584 T-Shirt Gumbo【二分図多重マッチング】

タイトルリンク:
http://poj.org/problem?id=2584
テーマ:
現在、5種類の型番(S、M、L、X、T)の服がN人の出場選手に配布されている.各参加者に必要な服の型番の範囲を与える.
この範囲内のモデルの参加者はみな受け入れられる.この5種類の服のそれぞれの数を与えると、問題は1つあるかどうかです.
割り当て案により、すべての参加選手が自分の型番の範囲内の服を手に入れることができる.
考え方:
二分図マッチングは1対1のマッチングであり,ここでは1対多マッチングであり,二分図多重マッチングのモデルで行う必要がある.具体的には
ハンガリーアルゴリズムのcy[MAXN]を2次元配列cy[MAXN][MAXN]に変更した.cy[i][j]は、要素yiに一致するj番目の要素を表す
素は、vey[i]とともに要素yiに一致する要素の数を記録する.
ACコード:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 33;

int Map[MAXN][MAXN];
bool Mask[MAXN];
int NX,NY,N;

int vcy[MAXN];
int cy[MAXN][MAXN];

int limit[MAXN];

bool FindPath(int u)
{
    for(int i = 1; i <= 5; ++i)
    {
        if(Map[u][i] && !Mask[i])
        {
            Mask[i] = 1;
            if(vcy[i] < limit[i])
            {
                cy[i][vcy[i]++] = u;
                return true;
            }

            for(int j = 0; j < limit[i]; ++j)
            {
                if(FindPath(cy[i][j]))
                {
                    cy[i][j] = u;
                    return true;
                }
            }
        }
    }
    return false;
}

void MulMatch()
{
    int Ans = 0;
    memset(vcy,0,sizeof(vcy));
    for(int i = 1; i <= N; ++i)
    {
        memset(Mask,0,sizeof(Mask));
        Ans += FindPath(i);

    }
    if(Ans == N)
        printf("T-shirts rock!
");
    else
        printf("I'd rather not wear a shirt anyway...
");
}

int main()
{
    char s[20];
    while(~scanf("%s",s))
    {
        if(strcmp(s,"ENDOFINPUT") == 0)
            break;
        scanf("%d",&N);
        memset(Map,0,sizeof(Map));
        for(int i = 1; i <= N; ++i)
        {
            scanf("%s",s);
            char a = s[0];
            char b = s[1];
            int u,v;
            if(a == 'S')
                u = 1;
            else if(a == 'M')
                u = 2;
            else if(a == 'L')
                u = 3;
            else if(a == 'X')
                u = 4;
            else if(a == 'T')
                u = 5;

            if(b == 'S')
                v = 1;
            else if(b == 'M')
                v = 2;
            else if(b == 'L')
                v = 3;
            else if(b == 'X')
                v = 4;
            else if(b == 'T')
                v = 5;
            for(int j = u; j <= v; ++j)
                Map[i][j] = 1;
        }
        for(int i = 1; i <= 5; ++i)
            scanf("%d",&limit[i]);
        scanf("%s",s);
        MulMatch();
    }

    return 0;
}