Ich trainiere Code-Probleme wie UvA und ich habe diese, in der ich muss, wenn ich eine Reihe von n Prüfungen und k Studenten eingeschrieben habe die Prüfungen, finden Sie heraus, ob es möglich ist, alle Prüfungen in zwei Zeitfenstern zu planen.
Eingabe Mehrere Testfälle. Jeder beginnt mit einer Zeile, die 1 & lt; n & lt; 200 von verschiedenen Untersuchungen geplant werden. Die zweite Zeile enthält die Anzahl der Fälle, in denen mindestens 1 Student in 2 Prüfungen eingeschrieben ist. Dann folgen k Zeilen, von denen jede zwei Zahlen enthält, die das Untersuchungspaar für jeden der obigen Fälle angeben. (Eine Eingabe mit n = 0 bedeutet Ende der Eingabe und soll nicht verarbeitet werden.)
Ausgabe: Sie müssen entscheiden, ob der Prüfungsplan für 2 Zeitfenster möglich oder nicht ist.
Beispiel:
Eingabe:
%Vor%Ausgabe:
%Vor%Ich denke, der allgemeine Ansatz ist Graph Coloring, aber ich bin wirklich ein Newb und ich gestehe, dass ich einige Probleme hatte, das Problem zu verstehen. Wie auch immer, ich versuche es und schicke es dann ein. Könnte mir bitte jemand helfen, Code für dieses Problem zu machen? Ich werde jetzt diesen Algo handhaben und verstehen müssen, um ihn später immer wieder zu verwenden.
Ich bevorzuge C oder C ++, aber wenn Sie wollen, ist Java in Ordnung für mich;)
Vielen Dank im Voraus
Ich habe den Pseudocode des Poly-Generators in den JAVA-Code übersetzt, um eine Lösung für mein Problem zu finden. Wir haben eine Submission-Plattform (wie uva / ACM-Wettbewerbe), daher weiß ich, dass es auch in dem Problem mit schwierigeren Fällen passiert ist.
Hier ist es:
%Vor%Ich habe noch nicht optimiert, ich habe nicht die Zeit richtig neu, aber wenn Sie wollen, können Sie / wir hier darüber diskutieren.
Ich hoffe, es gefällt euch! ;)
Sie haben Recht, dass es sich um ein Farbproblem handelt. Insbesondere müssen Sie bestimmen, ob das Diagramm 2-färbbar ist. Das ist trivial: Machen Sie ein DFS auf dem Graphen und färben Sie abwechselnd schwarze und weiße Knoten. Wenn Sie einen Konflikt finden, ist das Diagramm nicht 2-färbbar und die Planung ist unmöglich.
%Vor% Dies wird in O(|V| + |E|) mit Adjazenzliste ausgeführt.
In der Praxis stellt sich die Frage, ob man die n Untersuchungen in zwei Teilmengen A und B (zwei Zeitschlitze) aufteilen kann, so dass für jedes Paar in der Liste von k Untersuchungspaaren entweder a zu A gehört und b zu B gehört a gehört zu B und b gehört zu A.
Sie haben Recht, dass es ein Problem mit zwei Farben ist; es ist ein Graph mit n Ecken und es gibt einen ungerichteten Bogen zwischen den Ecken a und b, wenn das Paar oder in der Liste erscheint. Dann stellt sich die Frage nach der 2-Färbbarkeit des Graphen, wobei die beiden Farben die Partition zu den Zeitschlitzen A und B bezeichnen.
Ein 2-färbbarer Graph ist ein "zweiteiliger Graph". Sie können leicht auf Zweiparteilichkeit testen, siehe Ссылка .