图着色算法:典型的调度问题 [英] Graph colouring algorithm: typical scheduling problem
问题描述
我很喜欢阿姆斯特丹训练code问题,我有这个在我的有,给定一组的 N 考试和 K 学生报名参加了考试,查找是否有可能安排所有考试中的两个时隙的。
I'm training code problems like UvA and I have this one in which I have to, given a set of n exams and k students enrolled in the exams, find whether it is possible to schedule all exams in two time slots.
输入 若干测试案例。每个人开始含行 1< N'LT; 200 不同的考试,被调度。 第二行有病例数的 K ,其中至少存在1学生就读于2考试。然后, K 线条会随之而来,即指定一考试如上的情况下,每个含2个号码。 (其中n = 0的意志的输入装置输入的端,并且不被处理)。的
Input Several test cases. Each one starts with a line containing 1 < n < 200 of different examinations to be scheduled. The 2nd line has the number of cases k in which there exist at least 1 student enrolled in 2 examinations. Then, k lines will follow, each containing 2 numbers that specify the pair of examinations for each case above. (An input with n = 0 will means end of the input and is not to be processed).
输出: 你必须决定考试计划是否可以或不可以 2个时隙。的
Output: You have to decide whether the examination plan is possible or not for 2 time slots.
例如:
输入:
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
输出继电器:
Ouput:
NOT POSSIBLE.
POSSIBLE.
我觉得一般的方法是图着色的,但我真的对于新手,我可以承认,我遇到了一些麻烦理解问题。 无论如何,我想这样做,然后提交。 可能有人请帮我做一些code这个问题? 我将要处理,现在明白这个算法中,以便在以后使用它,一遍又一遍。
I think the general approach is graph colouring, but I'm really a newb and I may confess that I had some trouble understanding the problem. Anyway, I'm trying to do it and then submit it. Could someone please help me doing some code for this problem? I will have to handle and understand this algo now in order to use it later, over and over.
我preFER C或C ++,但如果你想,Java是没什么问题;)
I prefer C or C++, but if you want, Java is fine to me ;)
在此先感谢
推荐答案
我翻译polygenelubricant的伪code到JAVA code,以便为我的问题的解决方案。我们有一个提交平台(如UVA / ACM竞赛),所以我知道它通过甚至在问题多,最重的案件。
I've translated the polygenelubricant's pseudocode to JAVA code, in order to provide a solution for my problem. We have a submission platform (like uva/ACM contests), so I know it passed even in the problem with more and hardest cases.
这是:
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<Integer,String> exams = new Hashtable<Integer, String>();
ArrayList<Edge> edges = new ArrayList<Edge>();
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<Edge> edges,Hashtable<Integer,String> 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();
}
}
我没有优化的是,我没有足够的时间合适的新的,但如果你想,你/我们可以在这里讨论。
I didn't optimized yet, I don't have the time right new, but if you want, you/we can discuss it here.
希望你喜欢它! ;)
这篇关于图着色算法:典型的调度问题的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!