图着色算法：典型的调度问题 [英] 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＆LT; 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屋！