Untitled

mail@pastecode.io avatar
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;
}