[POJ]1679 The Unique MST

这道题要我们求最小生成树是不是唯一的，其实就是让我们求次小生成树，如果次小生成树和最小生成树的权值是一样的，说明最小生成树不唯一；反之说明唯一。
那么问题就转化为如何求次小生成树，首先我们可以用Prim或者Kruskal求得MST。那么对于其余所有不在MST里的边，我们可以枚举每次插入MST，那么MST一定以形成一个环。我们删除环上除了新插入边之外权值最大的边，那么新得到的生成树T就是包含被插入边的MST，但是显然这个时间复杂度太高了。如果对于新插入的边(u, v)，我们有更快的办法找到新形成的环上的除去新加入的边之外的最长边的话，就可以大大优化时间复杂度。Prim和Kruskal在这里就有一个非常好的应用：

• Kruskal算法中，我们每次取边e连接S和S'两个顶点集合的时候，e就是所有S中的节点u到S'中节点v路径上的最长边。证明显而易见，因为kruskal是按照边权值从小到大加的。
• Prim算法中，我们每次取连接顶点集S和V-S的边e(u, v)的时候，假设u是在S当中的节点，对于任意在S当中的节点i，其到v的路径上最长的边maxCost[i][v] = max(maxCost[i][u], e.cost)，我们只要一直维护maxCost矩阵就行。

所以我们在建立MST的时候就可以求得MST中任意两点(u, v)路径上最长的边，之后我们只需要枚举所有不在MST上的点来求次小生成树即可。建立MST的时间复杂度是O(E * log E)，求任意两点路径上的最长边时间复杂度O(V^2)，枚举每一条边的时间复杂度也是O(V^2)，所以总的时间复杂度是O(V^2 + E * log E)。代码如下：

Prim的做法:

	#include<cstdio>
	#include<cmath>
	#include<algorithm>
	#include<iostream>
	#include<cstring>
	#include<climits>
	#define INF 0x3f3f3f3f
	using namespace std;
	const int N = 105;
	int n,m;
	//maxCost[i][j] represents max edge on path from i to j in MST
	//used[u][v] represents if edge(u, v) is picked in MST
	int graph[N][N], maxCost[N][N], used[N][N];
	//let's say V is the set of total vertex and S is the set of vertex we already picked
	//minDist[i] represents minimum distance from S to node i in V - S, which can help us find
	//the edge that prim needs
	//visited keeps track of nodes in S
	//pre[i] represents where is the minDist[i] edge from
	int visited[N], minDist[N], pre[N];
	int prim()
	{
	//start from 1
	int curr = 1, totalW = 0;
	visited[curr] = true;
	//update minDist
	for(int i = 1; i <= n; ++i)
	{
	if(!visited[i]){
	minDist[i] = graph[curr][i];
	pre[i] = curr;
	}
	}
	//n - 1 edges to get
	for(int k = 1; k < n; ++k)
	{
	//find min edge between S and V - S
	int minEdge = INT_MAX;
	for(int i = 1; i <= n; ++i)
	{
	if(!visited[i] && minDist[i] < minEdge)
	{
	minEdge = minDist[i];
	curr = i;
	}
	}
	//now we have the edge picked
	//update maxCost, for every edge e we picked and its two nodes,
	//let's say v is the vertext in S and u is the vertex in V - S,
	//and i is one node in S which is not v, we have dp function
	//maxCost[i][u] = max(maxCost[i][v], e.cost)
	for(int j = 1; j <= n; ++j)
	{
	if(visited[j])
	{
	int maxEdge = max(maxCost[j][pre[curr]], minEdge);
	maxCost[j][curr] = maxEdge;
	maxCost[curr][j] = maxEdge;
	}
	}
	used[curr][pre[curr]] = 1;
	used[pre[curr]][curr] = 1;
	visited[curr] = 1;
	totalW += minEdge;
	//update minDist from S to V - S
	for(int j = 1; j <= n; ++j)
	{
	if(!visited[j] && graph[curr][j] < minDist[j])
	{
	minDist[j] = graph[curr][j];
	pre[j] = curr;
	}
	}
	}
	return totalW;
	}
	int findSecondMST()
	{
	int diff = INT_MAX;
	for(int i = 1; i <= n; ++i)
	{
	for(int j = 1; j <= n; ++j)
	{
	if(!used[i][j] && i != j && graph[i][j] != INT_MAX)
	{
	diff = min(diff, graph[i][j] - maxCost[i][j]);
	}
	}
	}
	return diff;
	}
	int main()
	{
	int t;
	cin >> t;
	while(t--){
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
	for(int j = 1; j <= n; j++)
	{
	if(i == j) graph[i][j]=0;
	else graph[i][j] = INT_MAX;
	}
	}
	for(int i = 0; i < m; i++){
	int u,v,w;
	cin >> u >> v >> w;
	graph[u][v] = graph[v][u] = w;
	}
	memset(visited, 0, sizeof(visited));
	memset(minDist, INF, sizeof(minDist));
	memset(maxCost, 0, sizeof(maxCost));
	memset(used, 0, sizeof(used));
	//use prim to calculate MST and maximum edge on the path from u to v in MST
	//u and v could be any node
	int mst = prim();
	//now we can calcuate second MST
	int diff = findSecondMST();
	if(!diff)
	printf("Not Unique!\n");
	else
	printf("%d\n", mst);
	}
	}

view raw POJ_1679_The Unique MST_prim.cpp hosted with ❤ by GitHub

Kruskal的做法:

	//POJ 1679
	/*
	Given a connected undirected graph, tell if its minimum spanning tree is unique.
	Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V', E'), with the following properties:
	1. V' = V.
	2. T is connected and acyclic.
	Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E') of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E'.
	Input
	The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.
	Output
	For each input, if the MST is unique, print the total cost of it, or otherwise print the string 'Not Unique!'.
	*/
	#include <cstdio>
	#include <cstring>
	#include <iostream>
	#include <algorithm>
	#include <string>
	#include <vector>
	#include <climits>
	#include <set>
	using namespace std;
	const int N = 105;
	int maxCost[N][N];
	int n,m;
	struct Edge
	{
	int u, v, w;
	bool used;
	};
	class UnionFind
	{
	public:
	UnionFind(int n)
	{
	m_uf = vector<int>(n, 0);
	m_sz = vector<int>(n, 1);
	m_adj = vector<set<int> >(n);
	for(int i = 0; i < n; ++i)
	m_uf[i] = i;
	}
	void connect(int i, int j)
	{
	int rootI = root(i), rootJ = root(j);
	if(rootI == rootJ)return;
	if (m_sz[rootI] <= m_sz[rootJ])
	{
	m_uf[rootI] = rootJ;
	m_sz[rootJ] += m_sz[rootI];
	}
	else
	{
	m_uf[rootJ] = rootI;
	m_sz[rootI] += m_sz[rootJ];
	}
	m_adj[rootI].insert(rootJ);
	m_adj[rootJ].insert(rootI);
	}
	bool find(int i, int j)
	{
	return root(i) == root(j);
	}
	vector<int> getNodesInSet(int i)
	{
	vector<int> set;
	getNodes(-1, 1, set);
	return set;
	}
	private:
	vector<int> m_uf;
	vector<int> m_sz;
	vector<set<int> > m_adj;//using adjacent list to keep track of what nodes are in current set
	int root(int i)
	{
	if (m_uf[i] == i)return i;
	int r = root(m_uf[i]);
	//update tree structure while doing path compression
	m_adj[i].erase(m_uf[i]);
	m_adj[m_uf[i]].erase(i);
	m_uf[i] = r;
	m_adj[i].insert(r);
	m_adj[r].insert(i);
	return r;
	}
	void getNodes(int from, int to, vector<int>& set)
	{
	//simple dfs
	set.push_back(to);
	for(std::set<int>::iterator iter = m_adj[to].begin(); iter != m_adj[to].end(); ++iter)
	if(*iter != from)getNodes(to, *iter, set);
	}
	};
	bool cmp(const Edge& lhs , const Edge& rhs) {
	return lhs.w < rhs.w;
	}
	int kruskal(vector<Edge>& edges)
	{
	UnionFind uf(n + 1);
	int k = 0, totalW = 0;
	for(int i = 0; i < edges.size(); ++i)
	{
	Edge& edge = edges[i];
	if(!uf.find(edge.u, edge.v))
	{
	uf.connect(edge.u, edge.v);
	edge.used = true;
	}
	else continue;
	//current edge is maximum edge between set which u is in and set which v belongs to
	//update maxCost
	++k;
	totalW += edge.w;
	vector<int> setU = uf.getNodesInSet(edge.u);
	vector<int> setV = uf.getNodesInSet(edge.v);
	for(int x = 0; x < setU.size(); ++x)
	{
	for(int y = 0; y < setV.size(); ++y)
	{
	int u = setU[x], v = setV[y];
	maxCost[u][v] = edge.w;
	maxCost[v][u] = edge.v;
	}
	}
	if(k >= n - 1)break;
	}
	return totalW;
	}
	int findSecondMST(vector<Edge>& edges)
	{
	int diff = INT_MAX;
	for(int i = 0; i < edges.size(); ++i)
	{
	Edge& edge = edges[i];
	if(!edge.used)
	diff = min(diff, edge.w - maxCost[edge.u][edge.v]);
	}
	return diff;
	}
	int main()
	{
	int T;
	scanf("%d",&T);
	while(T--)
	{
	memset(maxCost, 0, sizeof(maxCost));
	scanf("%d%d", &n, &m);
	vector<Edge> edges;
	for(int i = 0; i < m; i++)
	{
	Edge edge;
	scanf("%d %d %d", &edge.u, &edge.v, &edge.w);
	edge.used = false;
	edges.push_back(edge);
	}
	sort(edges.begin(), edges.end(), cmp);
	//calculate second MST to see if it has the same weight as MST
	//since there is only one edge different between MST and second MST
	//we can add every non-MST edge(u, v) once at a time to MST, there must be
	//a cycle, and we simply remove the edge with maximum cost on the path from
	//u to v in MST, we find the minimum cost for all these STs
	//to find maximum edge in path from u to v in MST, we can get when running
	//kruskal, since every time kruskal connects two different connected components
	//A and B with edge e, e is the maximum cost edge between every nodes in A and B
	//so we just need to know what nodes we have in A and B, we can use adjacent list
	//to keep track of this information in union find
	//run kruskal to get maximum edge for every two points in MST
	int mst = kruskal(edges);
	//find weight difference between mst and second mst
	int diff = findSecondMST(edges);
	if(!diff)
	printf("Not Unique!\n");
	else
	printf("%d\n", mst);
	}
	return 0;
	}

view raw POJ_1679_The Unique MST_kruskal.cpp hosted with ❤ by GitHub