poj 1679 The Unique MST (次小生成樹）
The Unique MST
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 20293
Accepted: 7124
Description
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!'.
Sample Input
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
Sample Output
3
Not Unique!
Source
次小生成樹問題，看了我好久，感覺還是差那麼一點點啊，看了好多大神的博客，自己重寫了一下，終於過了，思路還不是很清晰啊，prim算法中運用的dp的思想，對dp還是不怎麼懂啊，下階段要好好看看dp，krusal的次小生成樹還沒怎麼看懂，還是要多做題；
參考了博客http://blog.csdn.net/jarily/article/details/8912538
直接把其中的算法介紹部分轉過來啦，還是要多看幾遍
-
算法引入：
-
*設G=(V,E,w)是連通的無向圖,T是圖G的一棵最小生成樹;
-
*如果有另一棵樹T1,滿足不存在樹T’,ω(T’)<ω(T1),則稱T1是圖G的次小生成樹;
-
*
-
*算法思想：
-
*鄰集的概念:由T進行一次可行交換得到的新的生成樹所組成的集合,稱為樹T的鄰集,記為N(T);
-
*設T是圖G的最小生成樹,如果T1滿足ω(T1)=min{ω(T’)|T’∈N(T)},則T1是G的次小生成樹;
-
*首先先求該圖的最小生成樹T,時間復雜度O(Vlog2V+E);
-
*然後,求T的鄰集中權值和最小的生成樹,即圖G 的次小生成樹;
-
*如果只是簡單的枚舉,復雜度很高;
-
*首先枚舉兩條邊的復雜度是O(VE),再判斷該交換是否可行的復雜度是O(V),則總的時間復雜度是O(V2E);
-
*分析可知,每加入一條不在樹上的邊,總能形成一個環,只有刪去環上的一條邊,才能保證交換後仍然是生成樹;
-
*而刪去邊的權值越大,新得到的生成樹的權值和越小,可以以此將復雜度降為O(VE);
-
*更好的方法:首先做一步預處理,求出樹上每兩個結點之間的路徑上的權值最大的邊;
-
*然後枚舉圖中不在樹上的邊,有了預處理,就可以用O(1)的時間得到形成的環上的權值最大的邊;
-
*預處理:因為是一棵樹,只要簡單的BFS即可,預處理所要的時間復雜度為O(V2);
下面是用prim算法寫的代碼：
這裡面的用了一個path數組儲存兩點中權值最大的那條路徑；
low數組保存邊的權值；
用pre數組保存前驅的位置，用一個uesd數組標記是否在生成樹中；
#include
#include
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=100+5;
const int INF=0x3fffffff;
int map[maxn][maxn],low[maxn];
int path[maxn][maxn],pre[maxn];//從i到j的路徑上最大邊的權值
int visit[maxn],used[maxn][maxn];//標記數組
int n,m;
int prim()
{
int i,j,pos,mst=0;
memset(visit,0,sizeof(visit));//初始化
memset(path,0,sizeof(path));
memset(used,0,sizeof(used));
visit[1]=1;
for(i=1;i<=n;i++)
{
low[i]=map[1][i];
pre[i]=1;//記錄前驅
}
for(i=1;imap[pos][j])
{
low[j]=map[pos][j];//更新low數組
pre[j]=pos;
}
}
}
return mst;
}
int main()
{
int t,x,y,w,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
map[i][j]=INF;//把map初始化為INF
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&w);
map[x][y]=map[y][x]=w;
}
int mst;
int res=INF;
mst=prim();
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i!=j&& !used[i][j])
res=min(res,mst+map[i][j]-path[i][j]);//生成次小生成樹
}
if(res==mst)
puts("Not Unique!");
else
printf("%d\n",mst);
}
return 0;
}
如果生成的次小生成樹和最小生成樹相等說明不唯一，不相等說明唯一；
最小生成樹中加入一條邊，再刪除最小生成樹中的一條邊，就得到次小生成樹，這裡主要進行了預處理，對權值較大的路徑進行預處理。
這個博客的次小生成樹講的不錯 http://www.cnblogs.com/hxsyl/p/3290832.html
kruskal待更新；
