Tấn công thành trì
user_4303798
c_cpp
a year ago
2.4 kB
11
Indexable
#include<iostream> const int MAXSIZE = 100; int graph[MAXSIZE][MAXSIZE]; int visit[MAXSIZE]; int parent[MAXSIZE]; bool hasCycle; void resetVisit(int numFortress) { for (int i = 0; i < numFortress; i++) { visit[i] = 0; } } void resetGraph(int numFortress) { for (int i = 0; i < numFortress; i++) { for (int j = 0; j < numFortress; j++) { graph[i][j] = 0; } } } void readInput(int numFortress) { resetGraph(numFortress); for (int i = 0; i < numFortress; i++) { int id, numCannon, connectCount; std::cin >> id >> numCannon >> connectCount; for (int j = 0; j < connectCount; j++) { int connectTo; std::cin >> connectTo; graph[id][connectTo] += numCannon; // weighted graph graph[connectTo][id] += numCannon; } } } void resetParent(int numFortress) { for (int i = 0; i < numFortress; i++) { parent[i] = i; } } int result = 0; int findMinEdge(int v, int numFortress) { int min = graph[v][parent[v]]; int minP = v; for (int i = parent[v]; i != v ; i = parent[i]) { if (graph[i][parent[i]] < min) { min = graph[i][parent[i]]; minP = i; } } graph[minP][parent[minP]] = graph[parent[minP]][minP] = 0; return min; } void DFS_help(int v, int numFortress) { if (hasCycle) { return; } for (int i = 0; i < numFortress; i++) { if (graph[v][i] != 0) { if (visit[i] == 2 && parent[v] != i) { parent[i] = v; result += findMinEdge(i, numFortress); hasCycle = true; return; } else if (visit[i] == 0) { visit[i] = 2; parent[i] = v; DFS_help(i, numFortress); visit[i] = 1; } if (hasCycle) { break; } } } return; } void attack_help(int numFortress) { result = 0; while (true) { for (int i = 0; i < numFortress; i++) { resetVisit(numFortress); //resetParent(numFortress); hasCycle = false; if (visit[i] == 0 ) { parent[i] = -1; visit[i] = 2; DFS_help(i, numFortress); } } if (!hasCycle) { break; } } return; } int main() { freopen("input.txt", "r", stdin); int test; std::cin >> test; for (int t = 0; t < test; t++) { int numFortress; std::cin >> numFortress; readInput(numFortress); attack_help(numFortress); std::cout << result << "\n"; } return 0; }
Editor is loading...
Leave a Comment