the unique mst(prime，次小生成树判定).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 110;
int t,n,m;
int path[MAX][MAX];
int dmax[MAX][MAX];
struct node {
	int s,t;
	int dis;
	bool operator < (const node & tt) const {
		return dis > tt.dis;
	}
};
bool vis[MAX];
vector<node> tv;
int cost;

void prime() {
	int i,j;
	priority_queue<node> pq;
	node now, next;
	tv.clear();
	cost = 0;
	now.s = 0; now.t = 1; now.dis = 0;
	pq.push(now);
	for(i=0;i<n;i++) {
		while(true) {
			now = pq.top();
			pq.pop();
			if(!vis[now.t]) {
				vis[now.t] = true;
				break;
			}
		}
		path[now.s][now.t] = path[now.t][now.s] = -1;
		cost += now.dis;
		for(j=tv.size()-1;j>=0;j--) {
			node nt = tv[j];
			dmax[nt.t][now.t] = dmax[now.t][nt.t] = now.dis;
		}
		tv.push_back(now);
		next.s = now.t;
		for(j=1;j<=n;j++) {
			if(!vis[j] && path[next.s][j] != -1) {
				next.t = j;
				next.dis = path[next.s][j];
				pq.push(next);
			}
		}
	}
}

bool is_unique() {
	int i,j;
	for(i=1;i<=n;i++) {
		for(j=i+1;j<=n;j++) {
			if(path[i][j] != -1) {
				if(path[i][j] == dmax[i][j]) {
					return false;
				}
			}
		}
	}
	return true;
}

int main() {
	int i,j;
	scanf("%d", &t);
	while(t --) {
		scanf("%d %d", &n,&m);
		memset(path, -1, sizeof(path));
		memset(dmax, -1, sizeof(dmax));
		for(i=0;i<m;i++) {
			int x,y,z;
			scanf("%d %d %d", &x,&y,&z);
			path[x][y] = path[y][x] = z;
		}
		memset(vis, 0 ,sizeof(vis));
		prime();
		printf(is_unique() ? "%d\n" : "Not Unique!\n", cost);
	}
}