#include <stdio.h>
#include <string.h>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN = 21;

int n;
char judge[15], l, r;
int link[MAXN][MAXN];//服装所对应的人,link[i][j]表示第i种衣服的第j个人是几号
int visit[6], sum[6];
bool map[MAXN][6];//map[a][b]=1代表a,b顶点有边相连 　　

int count(char x)
{
	if (x == 'S')
		return 1;
	else if (x == 'M')
		return 2;
	else if (x == 'L')
		return 3;
	else if (x == 'X')
		return 4;
	else if (x == 'T')
		return 5;
}

bool dfs(int a)
{
	int i, j;
	for (i = 1; i <= 5; i++)
	{
		if (map[a][i] == true && visit[i] < sum[i])
		{
			visit[i]++;
			for (j = 1; j <= sum[i]; j++)
			{
				if (link[i][j] == 0 || dfs(link[i][j]))
				{
					link[i][j] = a;
					return true;
				}
			}
		}
	}
	return false;
}

int main()
{
	int i, j, s, e, ans=0;
	while (1)
	{
		scanf("%s", &judge);
		if (!strcmp(judge, "ENDOFINPUT"))
			break;
		scanf("%d", &n);
		for (i = 1; i <= n; i++)
		{
			scanf("%d", &l);//抵消\n
			scanf("%c%c", &l, &r);
			s = count(l);
			e = count(r);
			for (j = s; j <= e; j++)
				map[i][j] = true;
		}
		for (i = 1; i <= 5; i++)
			scanf("%d", &sum[i]);
		for (i = 1; i <= n; i++)
		{
			memset(visit, 0, sizeof(visit));
			if (dfs(i))
				ans++;
		}
		scanf("%s", &judge);//twice?
		if (ans == n)
			printf("T-shirts rock!\n");
		else
			printf("I'd rather not wear a shirt anyway...\n");
		memset(link, 0, sizeof(link));
		memset(map, 0, sizeof(map));
		ans = 0;
	}
}

• Re:二分匹配 dfs 0ms 水过，分享代码 (1720) 1505125851 2018-03-24 21:48:46