图着色算法:典型的调度问题

我正在训练像UvA这样的代码问题,我有这个问题,我必须考虑一组n个考试和k 参加考试的学生,找出是否可以在两个时间段安排所有考试

输入 几个测试用例。 每个人都以一行包含1 <n <200个不同的考试来开始。 第2行具有案例k的数量,其中至少有1名学生参加2次考试。 然后,将跟随k行,每行包含2个数字,用于指定上述每个案例的一对检查。 (n = 0的输入表示输入结束,不进行处理)。

输出: 您必须决定是否可以在2个时段进行检查计划。

例:

输入:

3 3 0 1 1 2 2 0 9 8 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 

输出继电器:

 NOT POSSIBLE. POSSIBLE. 

我认为一般的方法是图形着色,但我真的是一个新手,我可能会承认我在理解问题时遇到了一些麻烦。 无论如何,我正在努力做到然后提交它。 有人可以帮我为这个问题做一些代码吗? 我现在必须处理和理解这个算法,以便以后一遍又一遍地使用它。

我更喜欢C或C ++,但如果你愿意,Java对我来说很好;)

提前致谢

你是对的,这是一个图形着色问题。 具体而言,您需要确定图表是否为2色。 这是微不足道的:在图表上做一个DFS,为交替的黑白节点着色。 如果发现冲突,则图表不是2可着色的,并且调度是不可能的。

 possible = true for all vertex V color[V] = UNKNOWN for all vertex V if color[V] == UNKNOWN colorify(V, BLACK, WHITE) procedure colorify(V, C1, C2) color[V] = C1 for all edge (V, V2) if color[V2] == C1 possible = false if color[V2] == UNKNOWN colorify(V2, C2, C1) 

这在邻接列表中以O(|V| + |E|)

在实践中,问题是你是否可以将n个考试分成两个子集A和B(两个时隙),这样对于k个考试对的列表中的每一对,a属于A,b属于B,或属于B和b属于A.

你是对的,它是一个双色问题; 它是一个具有n个顶点的图形,如果该对或列表中出现,则顶点a和b之间存在无向弧。 然后问题是关于图的2可着色性,两种颜色表示分区到时隙A和B.

2可着色图是“二分图”。 您可以轻松测试二分性,请参阅http://en.wikipedia.org/wiki/Bipartite_graph 。

我已经将polygenelubricant的伪代码翻译成JAVA代码,以便为我的问题提供解决方案。 我们有一个提交平台(比如uva / ACM竞赛),所以我知道它在更多和最难的情况下通过了问题。

这里是:

 import java.util.ArrayList; import java.util.Hashtable; import java.util.Scanner; /** * * @author newba */ public class GraphProblem { class Edge { int v1; int v2; public Edge(int v1, int v2) { this.v1 = v1; this.v2 = v2; } } public GraphProblem () { Scanner cin = new Scanner(System.in); while (cin.hasNext()) { int num_exams = cin.nextInt(); if (num_exams == 0) break; int k = cin.nextInt(); Hashtable exams = new Hashtable(); ArrayList edges = new ArrayList(); for (int i = 0; i < k; i++) { int v1 = cin.nextInt(); int v2 = cin.nextInt(); exams.put(v1,"UNKNOWN"); exams.put(v2,"UNKNOWN"); //add the edge from A->B and B->A edges.add(new Edge(v1, v2)); edges.add(new Edge(v2, v1)); } boolean possible = true; for (Integer key: exams.keySet()){ if (exams.get(key).equals("UNKNOWN")){ if (!colorify(edges, exams,key, "BLACK", "WHITE")){ possible = false; break; } } } if (possible) System.out.println("POSSIBLE."); else System.out.println("NOT POSSIBLE."); } } public boolean colorify (ArrayList edges,Hashtable verticesHash,Integer node, String color1, String color2){ verticesHash.put(node,color1); for (Edge edge : edges){ if (edge.v1 == (int) node) { if (verticesHash.get(edge.v2).equals(color1)){ return false; } if (verticesHash.get(edge.v2).equals("UNKNOWN")){ colorify(edges, verticesHash, edge.v2, color2, color1); } } } return true; } public static void main(String[] args) { new GraphProblem(); } } 

我没有优化,我没有时间新的,但如果你想,你/我们可以在这里讨论它。

希望你喜欢它! ;)