Untitled
plain_text
2 months ago
1.9 kB
4
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]; 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) { dd[i] = 1; for (int j = 0; j < n; j++) { if (arr[i][j] != 0) { if (dd[j] == 1) { //push(j); truoc[j] = i; return; } else if (dd[j] == 0) { dd[j] = 1; truoc[j] = i; push(j); DFS(j); } } } } int main() { 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; } push(i); DFS(i); /*for (int i = 0; i < n; i++) { if (truoc[i] != -1) cout << truoc[i] << " -> " << i << " = " << arr[truoc[i]][i] << endl; } cout << endl;*/ int temp = truoc[i]; int min = arr[truoc[i]][i]; while (temp != i) { if (min > arr[temp][truoc[temp]]) min = arr[temp][truoc[temp]]; temp = truoc[temp]; } /*cout << "Min: " << min << endl;*/ if (i != truoc[truoc[i]]) { sum += min; } } cout << "Case #" << tc << endl << sum / 2 << endl; /*cout << endl; for (int i = 0; i < n; i++) { cout << truoc[i] << " "; }*/ } }