[ create a new paste ] login | about

Link: http://codepad.org/bV1vAwiF    [ raw code | fork ]

hoaithu.melody - C++, pasted on Jun 5:
//TanCongThanhTri

#include <iostream>

using namespace std;
const int MAXM = 205;

int T, M;
int mSoMayBanDa[MAXM], mMaTranKe[MAXM][MAXM], visit[MAXM], parent[MAXM];
int result, minEdge, startMinEdge, endMinEgde;
bool mCoChuTrinh;
void formatData() {
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			mMaTranKe[i][j] = 0;
		}
		visit[i] = 0;
		parent[i] = -1;
	}
	result = 0;
	mCoChuTrinh = false;
}

void findMinEdge(int stopVertex, int currentVertex) {
	if (currentVertex == stopVertex) {
		mMaTranKe[startMinEdge][endMinEgde] = 0;
		mMaTranKe[endMinEgde][startMinEdge] = 0;
		result += minEdge;
		for (int i = 0; i < M; i++) {
			visit[i] = 0;
			parent[i] = -1;
		}
		return;
	}
	if (mSoMayBanDa[currentVertex] + mSoMayBanDa[parent[currentVertex]] < minEdge) {
		minEdge = mSoMayBanDa[currentVertex] + mSoMayBanDa[parent[currentVertex]];
		startMinEdge = currentVertex;
		endMinEgde = parent[currentVertex];
	}
	findMinEdge(stopVertex, parent[currentVertex]);
}

void DFS(int v) {
	visit[v] = 1;
	for (int w = 0; w < M; w++) {
		if (mMaTranKe[v][w] == 1) {
			if (visit[w] == 0) {
				if (!mCoChuTrinh) {
					parent[w] = v;
					DFS(w);
				}
			}
			else if (w != parent[v]) {
				mCoChuTrinh = true;
				minEdge = mSoMayBanDa[w] + mSoMayBanDa[v];
				startMinEdge = w;
				endMinEgde = v;
				findMinEdge(w, v);
				return;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	//freopen("input.txt", "r", stdin);
	cin >> T;
	int id, soMayBanDa, soThanhLienKet, thanhLienKet;
	for (int tc = 1; tc <= T; tc++) {
		cin >> M;
		formatData();

		for (int m = 0; m < M; m++) {
			cin >> id >> soMayBanDa >> soThanhLienKet;
			mSoMayBanDa[id] = soMayBanDa;
			for (int i = 0; i < soThanhLienKet; i++) {
				cin >> thanhLienKet;
				mMaTranKe[id][thanhLienKet] = 1;
			}
		}
		for (int st = 0; st < M; st++) {
			do {
				mCoChuTrinh = false;
				for (int i = 0; i < M; i++) {
					visit[i] = 0;
					parent[i] = -1;
				}
				DFS(st);
			} while (mCoChuTrinh);
		}

		cout << result << endl;
	}
	return 0;
}


Output:
No errors or program output.


Create a new paste based on this one


Comments: