学步园

这是很简单的最大流的题目，问题的重点在于如何建图

题目大意：分配衬衫，将这些衬衫分给志愿者，每个志愿可以接受两种size，每种衣服的数量相同，每种衣服都有一手号（即从XS到XXL六个码）

求是否存在这样的分配

那么设0为原点，m+7为汇点，将六个型号分别设点

然后从原点到型号点的容量设为其数量（看题就知道了，数量很好求），从型号到每个志愿者连起来，容量为1，志愿者只需要一件衣服，从志愿者到汇点连线，容量为1

代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

const int N = 60;
const int inf = 99999999;
int n, m, T, s, t;
int cap[N][N], flow[N][N], p[N];

int maxFlow() {
    queue<int> q;
    int ans = 0, a[N];
    while( 1 ) {
        q.push(s);
        memset(a, 0, sizeof(a) );
        a[s] = inf;
        while ( !q.empty() ) {
            int u = q.front(); q.pop();
            for ( int i = 0; i <= t; ++i ) {
                if ( !a[i] && cap[u][i] > flow[u][i] ) {
                    p[i] = u; q.push(i);
                    a[i] = min( a[u], cap[u][i] - flow[u][i] );
                }
            }
        }
        if ( a[t] == 0 ) break;
        for ( int i = t; i != s; i = p[i] ) {
            flow[p[i]][i] += a[t];
            flow[i][p[i]] -= a[t];
        }
        ans += a[t];
    }
    return ans;
}
int num( string s ) {
    if ( s == "XS" ) return 1;
    else if ( s == "S") return 2;
    else if ( s == "M") return 3;
    else if ( s == "L") return 4;
    else if ( s == "XL") return 5;
    else if ( s == "XXL") return 6;
}
int main()
{
    scanf("%d", &T);
    while ( T-- ) {
        scanf("%d%d", &n, &m);
        getchar();
        s = 0, t = m + 7;
        int f = n/6;
        memset(flow, 0, sizeof(flow));
        memset(cap, 0, sizeof(cap));
        for ( int i = 7; i <= 6 + m; ++i )  {
            string size1, size2;
            cin >> size1 >> size2;
            cap[num(size1)][i]++;
            cap[num(size2)][i]++;
            cap[i][t] = 1;
        }
        for ( int i = 1; i <= 6; ++i )  {
            cap[0][i] += f;
        }
        for ( int i = 7; i < t; ++i ) cap[i][t] = 1;
        int ans = maxFlow();
        if ( ans < m ) printf("NO\n");
        else printf("YES\n");
    }
}