POJ 1679 次小生成树裸题

题意：

给定n个点m条无向带权边的图

问：是否最小生成树唯一

是则输出最小生成树的权值

思路：

求出次小生成树，判断权值是否于最小生成树相同即可。

dp[u][v]  表示在最小生成树下 [u,v] 路径中最大的边权值

每次BFS求出u点距离其他点的 路径上的最大边权值。

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
#define N 105
#define M 100005
#define inf 1000000
struct Edge{
	int from, to, dis, yes;
	bool operator<(const Edge&a)const{
		return a.dis>dis;
	}
}edge[M];

vector<int>G[N];
int f[N];
int find(int x){return x==f[x] ? x : f[x] = find(f[x]);}
bool Union(int x, int y){
	int fx = find(x), fy = find(y);
	if(fx == fy)return true;
	if(fx<fy)f[fx] = fy;
	else f[fy] = fx;
	return false;
}

int n, m, dp[N][N], dis[N][N], num;
int Kru(){
	int ans = 0;num = 0;
	sort(edge, edge+m);
	for(int i = 0; i < m; i++){
		int u = edge[i].from, v = edge[i].to;
		if(Union(u,v))continue;
		num++;
		ans += edge[i].dis;
		G[u].push_back(v),	G[v].push_back(u); 
		edge[i].yes = 1;
		dis[u][v] = dis[v][u] = edge[i].dis;
	}
	if(num == n-1)return ans;
	return -inf;
}
struct node{
	int maxdis, to, fa;
	node(int a=0,int c=0,int d=0):maxdis(a),to(c),fa(d){}
};
void BFS(int x){ 
	queue<node>q;
	q.push(node(0, x,-1));
	while(!q.empty()){
		node u = q.front(); q.pop();
		for(int i = 0; i < G[u.to].size(); i++){
			int v = G[u.to][i]; if(v == u.fa)continue;
			int nowmax = max(dis[u.to][v], u.maxdis);
			dp[x][v] = dp[v][x] = max(dp[x][v], nowmax);
			q.push(node(nowmax, v, u.to));
		}
	}
}

void init(){
	memset(dp, 0, sizeof(dp));
	for(int i = 1; i <= n; i++)
	{
		G[i].clear(), f[i] = i;
		for(int j = 1; j <= n; j++)dis[i][j] = inf;
		dis[i][i] = 0;
	}
}
int main(){
	int T, u, v, i, j;scanf("%d",&T);
	while(T--){
		scanf("%d %d",&n,&m);
		init();
		for(i = 0; i < m; i++)
		{
			scanf("%d%d%d",&edge[i].from, &edge[i].to, &edge[i].dis);
			u = edge[i].from, v = edge[i].to;
			edge[i].yes = false;
		}
		int mindis = Kru();
		for(i = 1; i <= n; i++) BFS(i);
		int ans = inf;
		
		for(i = 0; i < m; i++)if(!edge[i].yes)
		{
			int u = edge[i].from, v = edge[i].to;
			ans = min(ans, mindis + edge[i].dis - dp[u][v]);
		}
		if(ans == mindis)puts("Not Unique!");
		else printf("%d\n", mindis);
	}
	return 0;
}
/*
99
3 3
1 2 2
2 3 3
3 1 3
3 3
1 2 3
2 3 2
3 1 3
3 2
1 2 2
2 3 2




*/

POJ 1679 次小生成树裸题

原文：http://blog.csdn.net/acmmmm/article/details/18419267