pku 1679 The Unique MST
本文正體字版由OpenCC轉換
判斷一個圖的最小生成樹是否唯一，可以求其次小生成樹。如果它的次小生成樹權值之和等於最小生成樹權值之和，則最小生成樹不唯一，否則最小生成樹唯一。
求次小生成樹我的方法是O(N^2 + M)的。首先求出最小生成樹，記錄權值之和爲MinST。然後枚舉添加邊(u,v)，加上以後一定形成一個環，找到環上非(u,v)邊的權值最大的邊，把它刪掉，計算當前生成樹的權值之和，取所有枚舉加邊後生成樹權值之和的最小值，就是次小生成樹。
實際上具體更簡單的方法爲從每個頂點i，遍歷整個最小生成樹，定義F[j]爲從i到j的路徑上最大邊的權值，用O(N)的方法求出每個F[j]。然後枚舉頂點i的鄰域，遍歷每條不再最小生成樹中的邊(i,j)，加上這條邊，並刪除環上最大邊(非(i,j))，新的生成樹權值之和爲MinST + w(i,j) - F[j]，記錄其最小值即可，時間複雜度爲O(N^2 + M)。求最小生成樹可以用最簡單的Prim，時間複雜度爲O(N^2)，用更好的算法是沒有意義的。
這種方法比起那種求出最小生成樹後，枚舉刪除最小生成樹上每條邊，然後再求最小生成樹的方法應該要快些，因爲那種方法的時間複雜度爲O(N * ( N * logN + M) )(Prim + Heap)。
/*
* Problem: pku1679 The Unique MST
* Author: Guo Jiabao
* Time: 2009.4.14 8:28
* State: Solved
* Memo: 次小生成樹 Prim
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=101,MAXM=MAXN*MAXN*4,INF=0x7FFFFFFF;
using namespace std;
struct edge
{
edge *next,*op;
int t,c;
bool mst;
}ES[MAXM],*V[MAXN],*clst[MAXN],*NA[MAXN];
int N,M,EC,MinST,NMST,Ans;
int F[MAXN],MST[MAXN];
inline void addedge(edge **V,int a,int b,int c)
{
ES[++EC].next=V[a];
V[a]=ES+EC; V[a]->t=b; V[a]->c=c;
ES[++EC].next=V[b];
V[b]=ES+EC; V[b]->t=a; V[b]->c=c;
V[a]->op=V[b]; V[b]->op=V[a];
V[a]->mst=V[b]->mst=false;
}
void init()
{
int i,a,b,c;
scanf("%d%d",&N,&M);
EC=-1;Ans=INF;MinST=0;
memset(clst,0,sizeof(clst));
memset(V,0,sizeof(V));
memset(NA,0,sizeof(NA));
for (i=1;i<=M;i++)
{
scanf("%d%d%d",&a,&b,&c);
addedge(V,a,b,c);
}
}
void prim()
{
int i,j;
for (i=1;i<=N;i++)
MST[i]=INF;
for (i=1;;)
{
MST[i]=-INF;
for (edge *e=V[i];e;e=e->next)
{
if (e->c < MST[j=e->t])
{
MST[j]=e->c;
clst[j]=e->op;
}
}
int Mini=INF;i=0;
for (j=1;j<=N;j++)
if (MST[j]!=-INF && MST[j] < Mini)
{
Mini=MST[j];
i=j;
}
if (i==0)
break;
}
for (i=2;i<=N;i++)
{
MinST+=clst[i]->c;
j=clst[i]->t;
clst[i]->mst=true;
clst[i]->op->mst=true;
addedge(NA,i,j,clst[i]->c);
}
}
void dfs(int i)
{
for (edge *e=NA[i];e;e=e->next)
{
int j=e->t;
if (F[j]==-INF)
{
F[j]=F[i];
if (e->c > F[j])
F[j]= e->c;
dfs(j);
}
}
}
void smst()
{
int i,j;
for (i=1;i<=N;i++)
{
for (j=1;j<=N;j++)
F[j]=-INF;
F[i]++;
dfs(i);
for (edge *e=V[i];e;e=e->next)
{
j=e->t;
if (!e->mst)
{
NMST=MinST + e->c - F[j];
if (NMST < Ans)
Ans = NMST;
}
}
}
}
int main()
{
int T,i;
freopen("umst.in","r",stdin);
freopen("umst.out","w",stdout);
scanf("%d",&T);
for (i=1;i<=T;i++)
{
init();
prim();
smst();
if (Ans > MinST)
printf("%dn",MinST);
else
printf("Not Unique!n");
}
return 0;
}
上次修改時間 2017-02-03