Untitled
unknown
plain_text
a year ago
2.7 kB
23
Indexable
Never
#include <iostream> using namespace std; int n; int arr[101][101]; int dd[101]; int stk[101]; int stk_size; int truoc[101]; int mem; bool flag; void push(int num) { stk_size++; stk[stk_size] = num; } int top() { return stk[stk_size]; } void pop() { stk_size--; } bool empty() { if (stk_size == -1) return true; return false; } void DFS(int i, int par) { dd[i] = 1; for (int j = 0; j < n; j++) { if (arr[i][j] != 0) { if (dd[j] == 1) { if (j == par) continue; else if (j != par) { truoc[j] = i; mem = j; flag = true; return; } } else if (dd[j] == 0 && flag == false) { //cout << j << " "; dd[j] = 1; truoc[j] = i; DFS(j, i); } if (flag) { return; } } } } int main() { //freopen("vao.txt", "r", stdin); int t; cin >> t; for (int tc = 1; tc <= t; tc++) { int x, y, z, p; cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { arr[i][j] = 0; } } for (int i = 0; i < n; i++) { cin >> x >> y >> z; for (int j = 0; j < z; j++) { cin >> p; arr[x][p] += y; arr[p][x] += y; } } /*for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << arr[i][j] << " "; } cout << endl; }*/ int sum = 0; for (int i = 0; i < n; i++) { //cout << i << ": " << endl; stk_size = -1; for (int j = 0; j < n; j++) { dd[j] = 0; truoc[j] = -1; } //cout << "Chu trinh: " << i << " "; flag = false; DFS(i, -1); //cout << endl << "Mem: " << mem << endl; if (mem < n && mem >= 0) { if (arr[i][mem] != 0) truoc[i] = mem; } for (int k = 0; k < n; k++) { if (truoc[k] != -1) { //cout << truoc[k] << " -> " << k << " = " << arr[truoc[k]][k] << endl; } } if (flag) { int k = -1, h = -1; int min = -1; if (mem >= 0 && mem < n) { min = arr[truoc[mem]][mem]; k = truoc[mem]; h = mem; } int temp1 = mem; while (truoc[temp1] != mem) { temp1 = truoc[temp1]; //cout << truoc[temp1] << " " << temp1 << " " << arr[truoc[temp1]][temp1] << endl; if (min > arr[truoc[temp1]][temp1]) { min = arr[truoc[temp1]][temp1]; k = truoc[temp1]; h = temp1; } } sum += min; //cout << "Min: (" << k << "," << h << ") = " << min << endl; if (h >= 0 && h < n && k >= 0 && k < n) { arr[h][k] = 0; arr[k][h] = 0; } i--; } /*else { cout << "Ko CT" << endl; }*/ } cout << "Case #" << tc << endl << sum << endl; } return 0; }