agents
unknown
c_cpp
5 years ago
4.4 kB
4
Indexable
#include <iostream> #include <vector> using namespace std; vector<vector<int>> graph; vector<int> taken; vector<int> mapping; int As; int Bs; int aPlaced = 0; int bPlaced = 0; int singleA = 0; int singleB = 0; bool second = false; int bestScore; int graphSize; void swap(int *xp, int *yp) { int temp = *xp; *xp = *yp; *yp = temp; } vector<int> getSortedGraph() { vector<int> sizes(graphSize, 0); vector<int> newGraph(graphSize); for (int i = 0; i < graphSize; i++) { newGraph[i] = i; } for (int i = 1; i < graphSize; i++) { sizes[i] = graph[i].size(); } int i, j; for (i = 1; i < graphSize - 1; i++) { for (j = 1; j < graphSize - i - 1; j++) { if (sizes[j] < sizes[j + 1]) { swap(&sizes[j], &sizes[j + 1]); swap(&newGraph[j], &newGraph[j + 1]); } } } return newGraph; } int getMyScore(int IDX, bool A) { int score = 0; vector<int> neighbours = graph[IDX]; if (A) { for (int i = 0; i < neighbours.size(); i++) { //next to RED if (taken[neighbours[i]] == 1) { score += 2; } } } else { for (int i = 0; i < neighbours.size(); i++) { //next to RED if (taken[neighbours[i]] == 1) { score += 1; } //next to BLUE else if (taken[neighbours[i]] == 0) { score -= 1; } //free space else { score += 1; } } } return score; } int computeUpperBound() { int max = 0; int as = As - aPlaced; int bs = Bs - bPlaced; int i = 1; while (i < graphSize) { if (taken[mapping[i]] == -1) { if (bs > 0) { max += graph[mapping[i]].size(); bs--; } else if (as > 0) { max += graph[mapping[i]].size() * 2; as--; } else { break; } } i++; } return max; } void solve(int ags, int n, int score) { if (ags == 0) { //aagnets are placed, do the same for Bagents if (second) { if (score > bestScore) { bestScore = score; } return; } second = true; solve(Bs, 1, score); second = false; return; } if ((score + computeUpperBound()) <= bestScore) { return; } if (!second) { int tmp = 0; for (int i = n; i < graphSize; i++) { //free place in graph if (taken[mapping[i]] == -1) { taken[mapping[i]] = 1; singleA = getMyScore(mapping[i], true); aPlaced++; solve(ags - 1, i, score + singleA); taken[mapping[i]] = -1; aPlaced--; } } } else { for (int i = n; i < graphSize; i++) { //free place in graph if (taken[mapping[i]] == -1) { taken[mapping[i]] = 0; singleB = getMyScore(mapping[i], false); bPlaced++; solve(ags - 1, i, score + singleB); bPlaced--; taken[mapping[i]] = -1; } } } //second = false; } vector<vector<int>> loadData() { int nodes, edges; scanf("%d %d %d %d", &nodes, &edges, &As, &Bs); int cur = 0; int val = 0; vector<vector<int>> graph(nodes + 1); for (int i = 0; i < edges; i++) { scanf("%d %d", &cur, &val); graph[cur].push_back(val); graph[val].push_back(cur); } graphSize = graph.size(); taken = vector<int>(graphSize, -1); return graph; } int main() { int start = clock(); bestScore = 0; graph = loadData(); mapping = getSortedGraph(); solve(As, 1, 0); printf("%d\n", bestScore); int end = clock(); printf("It took %f seconds.\n", ((float)end - start) / CLOCKS_PER_SEC); }
Editor is loading...