Examination room arrangement
Name: Yang Xiaohua
【Problem Description】
It is necessary to perform the final exam, because many students don't stay in a course, so they can't
Two courses of the same student have arranged for the same examination, asked the last time for the final exam, how many times
Finish? (Tip: If the two courses are selected by the same class, there is a side between the vertices of the two lessons).
Design an algorithm, when given a picture, G = (V, E), | V | = N, (V
I, V
j)
ЄE, when there is only one classmate to choose the course I and course J, try to give an exam schedule N
1, N
2, N
3 ... NK, N
S∩nt = φ (s ≠ t, 1 ≤ S, T ≤ K) and v = N
I (1 ≤ i ≤ K).
【problem analysis】
This problem can be converted to a vertex color matching problem for a plan view, which is used both a backtrack solution. The selected per course is changed into a node. If a classmate is selected by the M (1 ≤ M ≤ N) door course, the nodes corresponding to the M gate course are connected to each other. Then the vertices of the adjacent edge cannot be the same color, which can neither arrange the same exam. However, this question is different from M-coloring problems, but the minimum scene is required, so the problem is to ask MIN-coloring problem, all the vertices can be used to color, the problem is solved.
【data structure】
Array TEST [
MAX] [
Max] to represent a picture g, where (i, j) is a side of G, then TEST [I] [j] = test [j] [i] = 1, otherwise TEST [i] [j] = test [J] [i] = 0, because this question only cares about whether a side is present, so use the adjacency matrix. The total number of colors is expressed in the number of total courses. Generation solution Use array value [
Max] to record, Value [
i] is the color of the node i, both of the course I can be arranged in Value [
i] field exam, result [
MAX] Used to record the optimal solution. The program in the program indicates the total course, and Minsum represents the least exam.
【Design and Analysis of Algorithms】
The function init () is read from the TestarRrange.in and establishes a corresponding adjacent matrix, and the adjacent matrix of the sample first set of data given in this program is shown in FIG. 2.
Function nextValue (k) is generated in the next color, before Value before this process [
1], Value [
2] ... Value [
K-1] There are different colors with different colors and adjacent sides. This process determines a value in the area [1, n] to Value [k], if there are some colors, they are allocated with the nodes adjacent to the node K, then the color allocation of the highest standard value is assigned. Give junction k, if there is no other color, set value [
K] = 0.
Function TestarRrange () is a recursive retrieval algorithm for the exam scheme, which calculates and identifies the minimum. If there is no color available, it is back. After the colors are allocated to the node k, the number of colors allocated at this time is made larger than the value of the minsum, then cut, and back. Before initially calling TestarRrange (1), set the initial value of the adjacency matrix of the diagram and the array value [
MAX] Set 0 value.
Function count () is a statistical number of colors allocated.
Function print () is a printing test site scheduled scheme. For each end node, in the worst case, the function nextValue () checks the availability of the color of each son node corresponding to the current extension point.
O (N)
2), therefore, the total time spent on the algorithm
ΣN
I (N
2) = n
2 (n
N-1) / (n-1) =
O (N)
N 1)
[Program List]
#include
#include
#include
#define max 10
INT Value [MAX], Result [MAX], TEST [MAX] [MAX], N, MINSUM = 0;
Void Init (file * fp) //
Read records from the file and establish an adjacency matrix corresponding to the course
{
INT A [max], t, j, i = 0;
Char Str [50], * P;
MEMSET (TEST, 0, SIZEOF (TEST));
FSCANF (FP, "% D", & n);
minsum = n;
FSeek (FP, 2, 1);
FGETS (STR, 50, fp);
P = STR;
While (1)
{
While (* p! = '/ n')
A [i ] = (int) STRTOL (P, & P, 10);
IF (a [0] == 0)
Break;
For (j = 0; j For (t = j 1; t TEST [A [J]] [A [T]] = TEST [A [T]] [A [J] = 1; i = 0; FGETS (STR, 50, fp); P = STR; } } INT Count (int * count, int K) // Statistics on the production of the solution to the scop { INT I, J, N = 0; For (i = 1; i <= k; i ) { For (j = i 1; j <= k; j ) IF (count [j] == count [i]) Break; IF (j == k 1) N ; } Return (N); } INT NEXTVALUE (INT K) // Generate the next solution { INT J, N = 0; While (1) { Value [K] = (Value [k] 1)% (N 1); IF (Value [K] == 0) Return 0; For (j = 1; j <= n; j ) // Legal examination of the generated solution { IF ((TEST [J] == 1) && (Value [K] == Value [J])) Break; } IF (j == n 1) { Return 0; } } } Int TestarRrange (INT K) //// Find a picture of a picture { INT J, T; While (1) { NextValue (k); IF (Value [K] == 0) Return 0; J = count (value, k); IF (j> minsum) {// If the total number of current genes is larger than the total number of previously generated, the pruning is made and traced back. For (t = k 1; t <= n; t ) Value [t] = 0; CONTINUE; } IF (k == n) { IF (j Record the minimum number of exams { minsum = j; For (t = 1; t <= n; t ) Result [T] = Value [T]; // Record the best solution } } Else TestarRrange (k 1); // Recursion call } } Void Print // // Print the examination scene { INT I, T, K, J = 1; IF (min == 1) // Just one place { Printf ("% d #:", J); For (i = 1; i <= n; i ) Printf ("% d", i); Printf ("/ n"); } ELSE IF (min == n) // A one { For (i = 1; i <= n; i ) Printf ("% d #:% d / n", i, i); } Else // Other situations { For (t = 1; t <= n; t ) { I = Result [T]; IF (i! = 0) { Printf ("% d #:", J ); For (k = T; k <= n; k ) { IF (Result [k] == i) { Printf ("% d", k); Result [k] = 0; } } Printf ("/ n"); } } } } void main () { File * fp; INT N, I; IF ((fp = fopen ("testarrange.in", "r")) == null) { Printf ("File Cann't Open!"); exit (0); } FSCANF (FP, "% D", & n); For (i = 0; i { INIT (FP); Memset (Value, 0, Sizeof (Value); TestarRrange (1); Printf ("Turns:% D / N TestarRrange Times:% D / N", i 1, minsum); PRINT (MINSUM); FSeek (FP, 2, 1); } Fclose (fp); } 【Instructions for use】 The first line of files represents a few sets of data. The next line is the total number of courses in the first group of data. N, followed by a few rows. The course selected by each student (the course selected by each student), ending the input with 0, and then a line of space, the following is the second set of data, the same as the previous description. Sample input: (The following data is file S7051B.IN content) 3 5 1 2 5 twenty four 1 2 3 5 4 5 3 5 twenty three 1 4 2 5 2 4 5 1 3 4 0 4 1 2 twenty three 3 4 1 4 0 4 1 2 3 4 0 Sample output: Turns: 1 TestarRange Times: 5 1 #: 1 2 #: 2 3 #: 3 4 #: 4 5 #: 5 Turns: 2 TestarRange Times: 2 1 #: 1 3 2 #: 2 4 Turns: 3 TestarRrange Times: 1 1 #: 1 2 3 4
