[ACM-ICPC] 5725 - Fun Coloring
Fun Coloring Problem
Instance: A
finite set U and sets S1, S2, S3,…,Sm
U and |Si|
≤ 3.
Problem: Is
there a function f : U 
{RED, BLUE} such that at least one member of each Si
is assigned a different color from the other members?
Given an instance of Fun Coloring Problem, your job is to find out whether such function f exists for the given instance.
Input
In this problem U = {x1, x2, x3,…,xn}. There are k instances of the problem. The first line of the input file contains a single integer k and the following lines describe k instances, each instance separated by a blank line. In each instance the first line contains two integers n and m with a blank in between. The second line contains some integers i’s representing xi’s in S1, each i separated by a blank. The third line contains some integers i’s representing xi’s in S2 and so on. The line m+2 contains some integers i’s representing xi’s in Sm. Following a blank line, the second instance of the problem is described in the same manner and so on until the kth instance is described. In all test cases, 1 ≤ k ≤ 13, 4 ≤ n ≤ 22, and 6 ≤ m ≤ 111.
Output
For each instance of the problem, if f exists, print a Y. Otherwise, print N. Your solution will contain one line of k Y’s (or N’s) without a blank in between. The first Y (or N) is the solution for instance 1. The second Y (or N) is the solution for instance 2, and so on. The last Y (or N) is the solution for instance k.
|
Sample input |
Sample output |
|
2 5 3 1 2 3 2 3 4 1 3 5
7 7 1 2 1 3 4 2 4 3 2 3 1 4 5 6 7
|
YN
|
窮舉所有 RED 與 GREEN 的放置方法，接著去查看每個集合不能全為 RED 或者 全為 GREEN。
#include <iostream>
#include <cstdio>
#include <sstream>
using namespace std;
int main() {
int t, n, m, i, j, k;
int sub[120][30], subt[120];
cin >> t;
string line;
while(t--) {
cin >> n >> m;
getline(cin, line);
for(i = 0; i < m; i++) {
getline(cin, line);
stringstream sin;
sin << line;
subt[i] = 0;
while(sin >> sub[i][subt[i]])
sub[i][subt[i]]--, subt[i]++;
}
int flag = 0;
for(i = (1<<n)-1; i >= 0; i--) {
for(j = 0; j < m; j++) {
int cnt = 0;
for(k = 0; k < subt[j]; k++)
cnt += (i>>sub[j][k])&1;
if(cnt == 0 || cnt == subt[j])
break;
}
if(j == m) {
flag = 1;
break;
}
}
if(flag) putchar('Y');
else putchar('N');
}
return 0;
}