Untitled

mail@pastecode.io avatarunknown
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] << " ";
		}*/
	}
}