import java.io.BufferedInputStream; import java.io.BufferedOutputStream; import java.io.Closeable; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.InputStream; import java.io.OutputStream; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.Random; public class _sol { // TODO MAKE THIS LIMIT TO 4500 private final static long TIME_LIMIT = 4500; private long startTime; /** Number of people */ private int n; /** Number of edges in friendship graph */ private int m; /** Number of tents */ private int v; /** Number of paths between tents */ private int r; /** friends[i][j] = j-th friend of person i */ private ArrayList[] friends; /** friendValuesMap[i].get(j) =value of friendship between person i and j */ private HashMap[] friendsValuesMap; /** friendsValue[i][j] = value of j-th friend of person i */ private ArrayList[] friendsValue; /** tents[i][j] = j-th neighbour tent of tent i */ private ArrayList[] tents; /** check fast if some tent is neighbour of another */ private HashSet[] tentsCheck; /** w[i] is the influence coefficient of person i */ private int[] w; /** d[i] is how many roads can person i help cleaning */ private int[] d; private int bestPerson = -1; private int bestPersonNumberOfFriends = -1; private int secondBestPerson = -1; private int secondBestPersonNumberOfRoads = -1; private int bestTent = -1; private int bestTentNumberOfRoads = -1; private int secondBestTent = -1; private int secondBestTentNumberOfRoads = -1; static Random random; private void solve() throws Exception { readInput(); int person, tent; int numberOfGeneratedSolutions = 0; random = new Random(181783497276652981L); Object[] result = newDummyResultStruct(); Integer rsc = (Integer) result[0]; Object[] current; while (getCurrentTime() < TIME_LIMIT) { switch (numberOfGeneratedSolutions) { case 0: person = bestPerson; tent = bestTent; break; case 1: person = bestPerson; tent = secondBestTent; break; case 2: person = secondBestPerson; tent = bestTent; break; case 3: person = secondBestPerson; tent = secondBestTent; break; default: person = random.nextInt(n); tent = random.nextInt(v); break; } current = generateNewResult(person, tent); numberOfGeneratedSolutions++; Integer csc = (Integer) current[0]; if (csc > rsc) { rsc = csc; result = current; } } // System.out.println(String.format("gen solutions: %d\nscore: %d", // numberOfGeneratedSolutions, rsc)); write(print(result)); } Object[] generateNewResult(int person, int tent) { Object[] result = newResultStruct(d); int[] newD = new int[n]; System.arraycopy(d, 0, newD, 0, n); boolean[] visitedPeople = new boolean[n]; boolean[] visitedTents = new boolean[v]; int[] tentPersonMap = new int[v]; int[] personTentMap = new int[n]; // START THE BFS FROM THE PEOPLE,TENT // { begin assign person in tent visitedPeople[person] = true; visitedTents[tent] = true; tentPersonMap[tent] = person; personTentMap[person] = tent; assignPersonToTent(result, person, tent); // } end assign person in tent ArrayList peoplesQueue = new ArrayList(); int peoplesQueueIdx = 0; peoplesQueue.add(person); while (peoplesQueueIdx < peoplesQueue.size()) { int personForVisit = peoplesQueue.get(peoplesQueueIdx++); if (newD[personForVisit] == 0) { continue; } int tentForPersonForVisit = personTentMap[personForVisit]; int neighbourTentIdx = 0; for (int neighbourIdx = 0; neighbourIdx < friends[personForVisit] .size(); ++neighbourIdx) { if (newD[personForVisit] == 0) { break; } int neighbour = friends[personForVisit].get(neighbourIdx); if (newD[neighbour] == 0) { continue; } if (visitedPeople[neighbour]) { // just clean path if there is edge in tents int neighbourTent = personTentMap[neighbour]; if (tentsCheck[neighbourTent] .contains(tentForPersonForVisit)) { newD[neighbour]--; newD[personForVisit]--; cleanPath(result, neighbour, personForVisit, friendsValuesMap[neighbour].get(personForVisit)); } continue; } for (; neighbourTentIdx < tents[tentForPersonForVisit].size(); ++neighbourTentIdx) { int neighbourTent = tents[tentForPersonForVisit] .get(neighbourTentIdx); if (visitedTents[neighbourTent]) { continue; } // assign person to this tent and clean path visitedPeople[neighbour] = true; visitedTents[neighbourTent] = true; newD[neighbour]--; newD[personForVisit]--; tentPersonMap[neighbourTent] = neighbour; personTentMap[neighbour] = neighbourTent; peoplesQueue.add(neighbour); assignPersonToTent(result, neighbour, neighbourTent); cleanPath(result, neighbour, personForVisit, friendsValuesMap[neighbour].get(personForVisit)); break; // end of assignPerson to this tent and clean path } } } calculateScore(result, w); return result; } @SuppressWarnings("unchecked") private void readInput() throws Exception { // BEGIN READ INPUT n = readNextInt(); w = new int[n]; d = new int[n]; friends = new ArrayList[n]; friendsValue = new ArrayList[n]; friendsValuesMap = new HashMap[n]; for (int i = 0; i < n; ++i) { friends[i] = new ArrayList(); friendsValue[i] = new ArrayList(); friendsValuesMap[i] = new HashMap(); } m = readNextInt(); int tmp1, tmp2, tmp3; for (int i = 0; i < m; i++) { tmp1 = readNextInt(); tmp2 = readNextInt(); tmp3 = readNextInt(); friends[tmp1].add(tmp2); friends[tmp2].add(tmp1); friendsValue[tmp1].add(tmp3); friendsValue[tmp2].add(tmp3); friendsValuesMap[tmp1].put(tmp2, tmp3); friendsValuesMap[tmp2].put(tmp1, tmp3); } for (int i = 0; i < n; ++i) { w[i] = readNextInt(); } for (int i = 0; i < n; ++i) { d[i] = readNextInt(); if (friends[i].size() > bestPersonNumberOfFriends) { bestPersonNumberOfFriends = friends[i].size(); bestPerson = i; } else if (d[i] > secondBestPersonNumberOfRoads) { secondBestPersonNumberOfRoads = d[i]; secondBestPerson = i; } } v = readNextInt(); tents = new ArrayList[v]; tentsCheck = new HashSet[v]; for (int i = 0; i < v; ++i) { tents[i] = new ArrayList(); tentsCheck[i] = new HashSet(); } r = readNextInt(); for (int i = 0; i < r; i++) { tmp1 = readNextInt(); tmp2 = readNextInt(); tents[tmp1].add(tmp2); tents[tmp2].add(tmp1); tentsCheck[tmp1].add(tmp2); tentsCheck[tmp2].add(tmp1); } // END READ INPUT for (int i = 0; i < v; ++i) { if (tents[i].size() > bestTentNumberOfRoads) { bestTentNumberOfRoads = tents[i].size(); bestTent = i; } else if (tents[i].size() > secondBestTentNumberOfRoads) { secondBestTentNumberOfRoads = tents[i].size(); secondBestTent = i; } } } private long getCurrentTime() { return System.currentTimeMillis() - startTime; } private InputStream inputStream; private BufferedInputStream bufferedInputStream; private OutputStream outputStream; private BufferedOutputStream bufferedOutputStream; private _sol() throws Exception { outputStream = new FileOutputStream("camp.out"); bufferedOutputStream = new BufferedOutputStream(outputStream); inputStream = new FileInputStream("camp.in"); bufferedInputStream = new BufferedInputStream(inputStream); } private void closeFiles() { Closeable[] streams = new Closeable[4]; streams[0] = bufferedInputStream; streams[1] = inputStream; streams[2] = bufferedOutputStream; streams[3] = outputStream; for (int i = 0; i < 4; ++i) { try { streams[i].close(); } catch (Exception e) { e.printStackTrace(); } } } String readStr() throws Exception { StringBuilder strB = new StringBuilder(); int c; boolean hasChars = false; while (((c = bufferedInputStream.read()) >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')) { hasChars = true; strB.append((char) c); } if (!hasChars && c == -1) { throw new Exception("EOF"); } return hasChars ? strB.toString() : null; } String readNextStr() throws Exception { String s; while ((s = readStr()) == null) { } return s; } private final static char ZERO_CHAR = '0'; private final static char NINE_CHAR = '9'; int readInt() throws Exception { int c; int res = 0; boolean hasNum = false; while ((c = bufferedInputStream.read()) >= ZERO_CHAR && c <= NINE_CHAR) { hasNum = true; res *= 10; res += c - ZERO_CHAR; } if (!hasNum && c == -1) { throw new Exception("EOF"); } return hasNum ? res : -1; } int readNextInt() throws Exception { int r; while ((r = readInt()) == -1) { } return r; } void write(String str) throws Exception { bufferedOutputStream.write(str.getBytes()); } public static void main(String[] args) throws Exception { _sol solver = new _sol(); solver.startTime = System.currentTimeMillis(); solver.solve(); solver.closeFiles(); } private static Object[] newDummyResultStruct() { /** score of the result struct */ int score = Integer.MIN_VALUE; /** Number of people in the team */ int k = 0; /** X[i] is the i-th person in the team */ ArrayList X = null; /** Y[i] is the tent of the i-th person */ ArrayList Y = null; /** Number of roads for cleaning */ int t = 0; /** P[i] is the first person that cleans road between him and Q[i] */ ArrayList P = null; /** Q[i] is the second person that cleans road between him and P[i] */ ArrayList Q = null; /** Edges for calculation of the result. */ ArrayList edges = null; /** Initial d */ int[] initD = null; /** New d used for calculating current result. */ int[] newD = null; /** Saves cleaned paths */ HashSet cleanedPaths = null; return new Object[] { score, k, X, Y, t, P, Q, edges, initD, newD, cleanedPaths }; } private static Object[] newResultStruct(int[] initD) { int score = Integer.MIN_VALUE; int k = 0; ArrayList X = new ArrayList(); ArrayList Y = new ArrayList(); int t = 0; ArrayList P = new ArrayList(); ArrayList Q = new ArrayList(); ArrayList edges = new ArrayList(); int[] newD = new int[initD.length]; System.arraycopy(initD, 0, newD, 0, initD.length); HashSet cleanedPaths = new HashSet(); return new Object[] { score, k, X, Y, t, P, Q, edges, initD, newD, cleanedPaths }; } private static void calculateScore(Object[] resStruct, int[] w) { resStruct[0] = 0;// score = 0; ArrayList edges = (ArrayList) resStruct[7]; for (int i = 0; i < edges.size(); ++i) { resStruct[0] = (Integer) resStruct[0] + edges.get(i); } int k = (Integer) resStruct[1]; int[] initD = (int[]) resStruct[8]; int[] newD = (int[]) resStruct[9]; ArrayList X = (ArrayList) resStruct[2]; for (int i = 0; i < k; ++i) { int person = X.get(i); resStruct[0] = (Integer) resStruct[0] + (initD[person] - newD[person]) * w[person]; } } private static void assignPersonToTent(Object[] S, int p, int t) { S[1] = (Integer) S[1] + 1; ((ArrayList) S[2]).add(p); ((ArrayList) S[3]).add(t); } private static void cleanPath(Object[] S, int fp, int sp, int fv) { HashSet cleanedPaths = (HashSet) S[10]; if (cleanedPaths.contains((fp << 15) + sp)) { return; } S[4] = (Integer) S[4] + 1; ((ArrayList) S[5]).add(fp); ((ArrayList) S[6]).add(sp); int[] newD = (int[]) S[9]; newD[fp]--; newD[sp]--; ((ArrayList) S[7]).add(fv); cleanedPaths.add((fp << 15) + sp); cleanedPaths.add((sp << 15) + fp); } private final static char NEWLINE_CHAR = Character.LINE_SEPARATOR; private final static char EMPTYSPACE_CHAR = ' '; private static String print(Object[] S) { int k = (Integer) S[1]; ArrayList X = (ArrayList) S[2]; ArrayList Y = (ArrayList) S[3]; int t = (Integer) S[4]; ArrayList P = (ArrayList) S[5]; ArrayList Q = (ArrayList) S[6]; StringBuilder resultBuilder = new StringBuilder(); resultBuilder.append(k).append(NEWLINE_CHAR); for (int i = 0; i < k; ++i) { resultBuilder.append(X.get(i)).append(EMPTYSPACE_CHAR) .append(Y.get(i)).append(NEWLINE_CHAR); } resultBuilder.append(t).append(NEWLINE_CHAR); for (int i = 0; i < t; ++i) { resultBuilder.append(P.get(i)).append(EMPTYSPACE_CHAR) .append(Q.get(i)).append(NEWLINE_CHAR); } return resultBuilder.toString(); }