Untitled
unknown
java
4 years ago
8.1 kB
5
Indexable
import java.io.*; public class Main2 { public static int noOfDivaOneRoles = 0; public static int noOfDivaTwoRoles = 0; public static int d1Index = 0; public static int d2Index = 0; public static int superIndex = 1; public static int actorsUsed = 0; // Antal skådespelare som fått roller public static boolean localMinima = false; public static boolean swapMade = true; public static int iSwap = 0; public static int jSwap = 0; public static void main(String args[]) throws FileNotFoundException { InputStream is = new FileInputStream("testinput.txt"); // Kattio io = new Kattio(System.in, System.out); Kattio io = new Kattio(is, System.out); int n = io.getInt(); // Antal roller i problemet. int s = io.getInt(); // Antal scener i problemet. int k = io.getInt(); // Antal skådespelare i problemet. int rolesActors[][] = new int[n][k + 1]; int scenesRoles[][] = new int[s][n + 1]; int rolePartners[][] = new int[n + 1][(n * n) + 1]; int divaOneRoles[] = new int[n]; int divaTwoRoles[] = new int[n]; int usedActors[] = new int[n]; int sol[][] = new int[n * k + 2][n + 2]; // Lösningsarray. // Initialize number of roles to 0. for (int i = 0; i < n + 1; i++) { rolePartners[i][0] = 0; } // Fyll 2d array med alla roller och vilka skådisar som kan spela respektive // roll. int available = 0; for (int i = 0; i < n; i++) { available = io.getInt(); rolesActors[i][0] = available; // System.out.print("roleActors[" + i + "][0]: " + rolesActors[i][0] + " "); for (int j = 1; j <= available; j++) { rolesActors[i][j] = io.getInt(); // System.out.print("roleActors[" + i + "][" + j + "]: " + rolesActors[i][j] + " // "); if (rolesActors[i][j] == 1) { divaOneRoles[noOfDivaOneRoles] = i + 1; noOfDivaOneRoles++; } else if (rolesActors[i][j] == 2) { divaTwoRoles[noOfDivaTwoRoles] = i + 1; noOfDivaTwoRoles++; } } } // Fyll 2d array med alla scener och vilka roller som är i respektive scen. for (int i = 0; i < s; i++) { int incr = 0; available = io.getInt(); scenesRoles[i][0] = available; for (int j = 1; j <= available; j++) { scenesRoles[i][j] = io.getInt(); } for (int p = 1; p <= scenesRoles[i][0]; p++) { for (int e = 1; e <= scenesRoles[i][0]; e++) { rolePartners[scenesRoles[i][p]][0] += 1; incr = rolePartners[scenesRoles[i][p]][0]; rolePartners[scenesRoles[i][p]][incr] = scenesRoles[i][e]; } } } int d1d2[] = new int[2]; d1d2 = getDivas(divaOneRoles, divaTwoRoles); // This could go bad if no solution exists but we naively // do it this way because the lab says there always is a solution while (checkRoleScenes(d1d2, rolePartners)) { d1d2 = getDivas(divaOneRoles, divaTwoRoles); } sol = insertActor(d1d2[0], 1, sol); sol = insertActor(d1d2[1], 2, sol); usedActors[0] = 1; usedActors[1] = 2; int usedIndex = 2; actorsUsed += 2; int superActor = k + 1; int[] r1r2 = new int[2]; boolean found = false; boolean roleCheck = true; // Create starting graph. --- HÄRIFRÅN ÄR DET RELEVANT, och variablerna ovan. for (int i = 0; i < n; i++) { if (d1d2[0] == i + 1 || d1d2[1] == i + 1) { continue; } for (int j = 1; j <= rolesActors[i][0]; j++) { if (rolesActors[i][j] == 1 || rolesActors[i][j] == 2) { continue; } if (!checkTaken(rolesActors[i][j], usedActors)) { usedActors[usedIndex] = rolesActors[i][j]; sol = insertActor(i + 1, rolesActors[i][j], sol); actorsUsed++; usedIndex++; found = true; break; } else { for (int m = 0; m < sol[rolesActors[i][j]][1]; m++) { r1r2[0] = i + 1; r1r2[1] = sol[rolesActors[i][j]][m + 2]; roleCheck = checkRoleScenes(r1r2, rolePartners); if (roleCheck) { break; } } if (!roleCheck) { sol = insertActor(i + 1, rolesActors[i][j], sol); found = true; roleCheck = true; break; } } } if (!found) { sol = insertActor(i + 1, superActor, sol); superActor++; actorsUsed++; } found = false; } // ------------------FRAM TILLS HIT, IGNORERA RESTEN System.out.println(actorsUsed); printSol(sol); io.close(); } private static boolean checkRolePossible(int actor, int role, int[][] ra) { for (int i = 1; i < ra[role - 1].length; i++) { if (ra[role - 1][i] == actor) { return true; } } return false; } private static void printSol(int[][] sol) { boolean nullRow = false; for (int i = 0; i < sol.length; i++) { if (sol[i][0] == 0) { continue; } for (int j = 0; j < sol[i].length; j++) { if (sol[i][j] == 0) { break; } System.out.print(sol[i][j] + " "); } System.out.println(""); } } private static int[][] insertActor(int role, int actor, int[][] sol) { sol[actor][0] = actor; sol[actor][1] += 1; sol[actor][sol[actor][1] + 1] = role; return sol; } private static boolean checkTaken(int actor, int[] usedActors) { for (int i = 0; i < usedActors.length; i++) { if (usedActors[i] == actor) { return true; } } return false; } private static boolean checkRoleScenes(int[] r1r2, int[][] rolePartners) { int max = 0; int role = 0; int role2 = 0; if (rolePartners[r1r2[0]][0] > rolePartners[r1r2[1]][0]) { max = rolePartners[r1r2[1]][0]; role = r1r2[1]; role2 = r1r2[0]; } else { max = rolePartners[r1r2[0]][0]; role = r1r2[0]; role2 = r1r2[1]; } for (int i = 1; i <= max; i++) { if (rolePartners[role][i] == role2) { return true; } if (rolePartners[role][i] == 0) { return false; } } return false; } private static int[] getDivas(int[] d1r, int[] d2r) { int[] d1d2 = new int[2]; for (int i = d1Index; i < noOfDivaOneRoles; i++) { for (int j = d2Index; j < noOfDivaTwoRoles; j++) { if (d1r[i] != d2r[j]) { d1d2[0] = d1r[i]; d1d2[1] = d2r[j]; d2Index++; return d1d2; } d2Index++; } d2Index = 0; d1Index++; } return d1d2; } }
Editor is loading...