Untitled

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