Untitled
unknown
plain_text
a year ago
2.0 kB
3
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){ mem = j; flag = true; return; } } else if (dd[j] == 0 && flag == false) { dd[j] = 1; truoc[j] = i; DFS(j, i); } } } } 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; int min = 1e9+7; for (int i = 0; i < 1; i++) { //cout << i << ": " << endl; stk_size = -1; for (int j = 0; j < n; j++) { dd[j] = 0; truoc[j] = -1; } flag = false; DFS(i, -1); //cout << "Mem: " << mem << endl; if(arr[i][mem] != 0) truoc[i] = mem; int w = -1, e = -1; for (int k = 0; k < n; k++) { if (truoc[k] != -1){ if(arr[truoc[k]][k] < min){ min = arr[truoc[k]][k]; w = truoc[k]; e = k; } } //cout << truoc[i] << " -> " << i << " = " << arr[truoc[i]][i] << endl; } sum += min; arr[w][e] = 0; arr[e][w] = 0; if(flag == true){ i--; } } cout << "Case #" << tc << endl << sum << endl; } return 0; }