[UVA][二分圖] 11045 - My T-shirt suits me
My T-shirt suits me
| My T-shirt suits me |
Our friend Victor participates as
an instructor in an environmental volunteer program. His boss asked Victor to distribute
N T-shirts to M volunteers, one T-shirt each volunteer, where N is multiple of
six, and N
M. There are the same number of T-shirts of each
one of the six available sizes: XXL, XL, L, M , S, and XS. Victor has a little
problem because only two sizes of the T-shirts suit each volunteer.
You must write a program to decide if Victor can distribute T-shirts in
such a way that all volunteers get a T-shirt that suit them. If N 
M, there can be some remaining T-shirts.
Input
The first line of the input
contains the number of test cases. For each test case, there is a line with two numbers N and M. N is
multiple of 6,
1
N36, and indicates the number of T-shirts. Number M,
1M30, indicates the number of volunteers, with NM. Subsequently, M lines are listed where each line contains, separated by
one space, the two sizes that suit each volunteer (XXL, XL, L, M , S, or XS).
Output
For each test case you are to print a line containing YES if there is, at least, one distribution where T-shirts suit all volunteers, or NO, in other case.
Sample Input
3 18 6 L XL XL L XXL XL S XS M S M L 6 4 S XL L S L XL L XL 6 1 L M
Sample Output
YES NO YES
照理講應該不會過得, 不過測資很水, 用 dfs 就過了, 就不必使用最大匹配了
#include <stdio.h>
#include <string.h>
const char s[][4] = {"XXL", "XL", "L", "M", "S", "XS"};
int code(const char *str) {
static int i;
for(i = 0; i < 6; i++)
if(!strcmp(s[i], str))
return i;
}
int map[30][2], flag, used[6];
int n, m, t;
void dfs(int idx) {
if(flag)
return;
if(idx == m) {
flag = 1;
return;
}
if(used[map[idx][0]] > 0) {
used[map[idx][0]]--;
dfs(idx+1);
used[map[idx][0]]++;
}
if(used[map[idx][1]] > 0) {
used[map[idx][1]]--;
dfs(idx+1);
used[map[idx][1]]++;
}
}
int main() {
char str[20];
int i, num;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
n = n/6;
for(i = 0; i < m; i++) {
scanf("%s", str);
num = code(str);
map[i][0] = num;
scanf("%s", str);
num = code(str);
map[i][1] = num;
}
for(i = 0; i < 6; i++)
used[i] = n;
flag = 0;
dfs(0);
if(flag)
puts("YES");
else
puts("NO");
}
return 0;
}