首页 > 专题系列 > Java解POJ > POJ 1679 The Unique MST [解题报告] Java
2013
11-10

POJ 1679 The Unique MST [解题报告] Java

The Unique MST

问题描述 :

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’.

输入:

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.

输出:

For each input, if the MST is unique, print the total cost of it, or otherwise print the string ‘Not Unique!’.

样例输入:

2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2

样例输出:

3
Not Unique!

解题代码:

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Edge{
	int u,v,disten;
	void set(int u,int v,int disten){
		this.u = u;
		this.v = v;
		this.disten = disten;
	}
}
interface MST{
	int N = 100+2,BIG = 1000000000;
	int getMST(int op);
}
class UniqueMST implements MST{
	int n,m;
	Edge edge[] = new Edge[N];
	int Graph[][] = new int[N][N];
	
	UniqueMST(){
		for(int i=0;i< N;++i){
			edge[i] = new Edge();
		}
	}
	
String Unique(){
	int ans = -1;
	ans = getMST(0);
	for(int i=0;i< n-1;++i){
	 Graph[edge[i].u][edge[i].v] = Graph[edge[i].v][edge[i].u] = BIG;
	 int cnt = getMST(1);
	 if(ans==cnt) return "Not Unique!";
	 Graph[edge[i].u][edge[i].v] = Graph[edge[i].v][edge[i].u] = edge[i].disten;
	}
	return String.valueOf(ans);
}

public int getMST(int op){
	int ans = 0;
	int meat[][] = new int[2][N];
	boolean s[] = new boolean[N];
	Arrays.fill(s, false);
	s[1] = true;meat[1][1] = 0;meat[0][1] = 1;
	for(int i=2;i<=n;++i){
	 meat[0][i] = 1;	//meat[0][i]记录当前到i的前结点是谁。
	 meat[1][i] = Graph[1][i];	//meat[1][i]记录到i的最小距离。
	}
	
    for(int i=0;i< n-1;++i){
			
	int k=-1,Min = 0;
	for(int j=1;j<=n;++j) if(!s[j]){
		if(k==-1 || (k!=-1 && meat[1][j]< Min)){
			k = j;
			Min = meat[1][j];
		}
	}
	if(op==0){
		edge[i].set(meat[0][k], k, Min);
	}
	ans+=Min;
	s[k] = true;
	for(int j=1;j<=n;++j) if(!s[j]){
		if(Graph[k][j]< meat[1][j]){
			meat[0][j] = k;
			meat[1][j] = Graph[k][j];
		}
	}
    }
   return ans;
 }
 
void initGraph(){
	for(int i=0;i< N;++i){
		for(int j=0;j< N;++j) Graph[i][j] = BIG;
	}
 }
 void addEdge(Edge e){
	Graph[e.v][e.u] = Graph[e.u][e.v] = e.disten;
 }
}
public class Main {
	
 public static void main(String[]args)throws Exception{
  UniqueMST uniqueMst = new UniqueMST();
	
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		
  int Case = GetNum(cin);
  Edge edge = new Edge();
  while(Case--!=0){
	uniqueMst.n = GetNum(cin);
	uniqueMst.m = GetNum(cin);
	uniqueMst.initGraph();
	for(int i=0;i< uniqueMst.m;++i){
		edge.set(GetNum(cin), GetNum(cin), GetNum(cin));
		uniqueMst.addEdge(edge);
	}
	System.out.println(uniqueMst.Unique());
   }
 }

 static int GetNum(StreamTokenizer cin)throws Exception{
	cin.nextToken();
	return (int) cin.nval;
	}
}