w********s
发帖数: 1570 | 1 一个国家的国旗可以有n种颜色组成，比如美国的国旗有红蓝白组成，全球有200个国家
，问最少需要几种颜色，可以涵盖所有国家国旗的颜色?
某个国家的国旗颜色为{c1, c2, c3}，那么c1 or c2 or c3可以涵盖。
e.g
f1=A
f2=C
f3=B,A
f4=B,C
f5=B,A
f6=B,C
那么最少A,C可以涵盖f1-f6。
贪心的话显然有问题，B(涵盖f3-f6),C(f2),A(f1)需要三种颜色 |
C******w
发帖数: 23 | |
C******w
发帖数: 23 | |
l*********8
发帖数: 4642 | 4 你举得例子什么意思？
f3和f5， f4和f6是一样的？
【在 w********s 的大作中提到】
: 一个国家的国旗可以有n种颜色组成，比如美国的国旗有红蓝白组成，全球有200个国家
: ，问最少需要几种颜色，可以涵盖所有国家国旗的颜色?
: 某个国家的国旗颜色为{c1, c2, c3}，那么c1 or c2 or c3可以涵盖。
: e.g
: f1=A
: f2=C
: f3=B,A
: f4=B,C
: f5=B,A
: f6=B,C
|
s******u
发帖数: 550 | 5 你能把题目说清楚点吗，比如你的每个变量都是什么意思？你的例子完全看不懂 |
m*****n
发帖数: 2152 | 6 BFS可以解决，但是可能不是最好的解法。
先inverse table，
c1 -> {f1, f2, ......}
c2 -> {f1, f2, ......}
C++可以用bitset, map["c1"] = bitset; ....
然后构造另一个bitset，所有bit全0，叫search。
然后BFS，每次 search | map["c?"]，
如果bit不全1，push search in list, 下一个。
直到找到search bit全1为止。
然后BFS的层数就是答案。
|
w********s
发帖数: 1570 | 7 对，某些国家的国旗可以是同样的颜色
比如f1,f2,f3,..f200表示200个国家的国旗
fn={c1,c2,...ck}表示有k中颜色
【在 l*********8 的大作中提到】
: 你举得例子什么意思？
: f3和f5， f4和f6是一样的？
|
w********s
发帖数: 1570 | 8 举个更直观点的
中国国旗={红色，黄色}
美国国旗={红色，蓝色，白色}
日本国旗={红色，白色}
巴基斯坦国旗={白色，绿色}
那么结果就是{红色，绿色}，任何以上的国旗至少都有红色or绿色中的一种。
【在 s******u 的大作中提到】
: 你能把题目说清楚点吗，比如你的每个变量都是什么意思？你的例子完全看不懂
|
g*********e
发帖数: 14401 | 9 用maximun flow. Create a graph such that each color represent one node,
and each national represent one node. Add a directed edge from color to
nation if that nation has such color in its flag. all edge has weigh 1.
Find the minimum cut. |
s******u
发帖数: 550 | 10 正解 用Dijkstra's algorithm
用maximun flow.
【在 g*********e 的大作中提到】
: 用maximun flow. Create a graph such that each color represent one node,
: and each national represent one node. Add a directed edge from color to
: nation if that nation has such color in its flag. all edge has weigh 1.
: Find the minimum cut.
|
|
|
m*****n
发帖数: 2152 | 11 你们没看懂题目吧？
【在 g*********e 的大作中提到】
: 用maximun flow. Create a graph such that each color represent one node,
: and each national represent one node. Add a directed edge from color to
: nation if that nation has such color in its flag. all edge has weigh 1.
: Find the minimum cut.
|
h***n
发帖数: 1600 | 12 只需2 种颜色，一种颜色做底色，另一种颜色用做pattern。 |
b*****n
发帖数: 2333 | 13 BFS那块不是很清楚 能再说详细点么 谢谢
【在 m*****n 的大作中提到】
: BFS可以解决，但是可能不是最好的解法。
: 先inverse table，
: c1 -> {f1, f2, ......}
: c2 -> {f1, f2, ......}
: C++可以用bitset, map["c1"] = bitset; ....
: 然后构造另一个bitset，所有bit全0，叫search。
: 然后BFS，每次 search | map["c?"]，
: 如果bit不全1，push search in list, 下一个。
: 直到找到search bit全1为止。
: 然后BFS的层数就是答案。
|
m*****n
发帖数: 2152 | 14 void BFS(Queue > que)
{
while(!que.empty())
{
for(int i=0; i
{
bitset search = que.front() | map_color[i];
if(search.all()) break; // fount it
else que.push(search);
}
que.pop();
}
}
【在 b*****n 的大作中提到】
: BFS那块不是很清楚 能再说详细点么 谢谢
|
P*******L
发帖数: 2637 | 15 如果
f1 = a, b
f2 = b, c
f3 = c, a
结果就得是 a, b, c 了？
【在 w********s 的大作中提到】
: 一个国家的国旗可以有n种颜色组成，比如美国的国旗有红蓝白组成，全球有200个国家
: ，问最少需要几种颜色，可以涵盖所有国家国旗的颜色?
: 某个国家的国旗颜色为{c1, c2, c3}，那么c1 or c2 or c3可以涵盖。
: e.g
: f1=A
: f2=C
: f3=B,A
: f4=B,C
: f5=B,A
: f6=B,C
|
b*****n
发帖数: 2333 | 16 谢谢！ 我再研究研究！
【在 m*****n 的大作中提到】
: void BFS(Queue > que)
: {
: while(!que.empty())
: {
: for(int i=0; i: {
: bitset search = que.front() | map_color[i];
: if(search.all()) break; // fount it
: else que.push(search);
: }
|
w********s
发帖数: 1570 | 17 yes.
【在 P*******L 的大作中提到】
: 如果
: f1 = a, b
: f2 = b, c
: f3 = c, a
: 结果就得是 a, b, c 了？
|
l***i
发帖数: 1309 | |
z****8
发帖数: 5023 | |
h*****u
发帖数: 109 | 20 这个是set partitioning problem, NP-hard in strong sense.
能有polynomial solution 吗？ 用maximum flow如何保证每个national node 有正好
的color?
用greedy heuristic吧。 |
|
|
g*********e
发帖数: 14401 | 21
我搞错了。应该是set cover 还是edge cover的问题
【在 h*****u 的大作中提到】
: 这个是set partitioning problem, NP-hard in strong sense.
: 能有polynomial solution 吗？ 用maximum flow如何保证每个national node 有正好
: 的color?
: 用greedy heuristic吧。
|
w********s
发帖数: 1570 | 22 how to do it？
【在 g*********e 的大作中提到】
:
: 我搞错了。应该是set cover 还是edge cover的问题
|
g*********e
发帖数: 14401 | |
f******n
发帖数: 279 | |
