题意:给定一个无向连通图,问该图的最小生成树是否唯一。
分析:有一个定理,如果该图存在次小生成树(与原最小生成树不同,但长度小于等于原最小生成树),则一定可以通过从原最小生成树中去掉一个边并再入一个边得到。
经过思考我们会发现,如果要加入一个v1和v2之间的新边,那么则应去掉原有的两点间通路(是唯一通路)中的一条边才能构成生成树。那么为了保证生成树最小,则应去掉原通路上最长的那条边。
对于本题我们的做法是先求最小生成树,然后枚举每一条没有在最小生成树中的边,看加入树中并去掉通路上的最长边后是否与原最小生成数长度相同。
那么如何才能知道要去掉的最长边有多长呢?我们可以在求最小生成树的时候使用Prim算法,我们用一个二维数组f[i][j]记录两点间走树枝路径的最长边。每将一个点加入到最小生成树中的时候,就更新所有已经在最小生成树中的点到该点的路径上的最长边长度。这样建树之后我们便知道了任意两点间的最长边长度。
//poj1679
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INFINITE 900000000 const int maxn = ; struct XEdge
{
int s;
int v; //边端点
int w; //边权值
XEdge(int s_ = , int v_ = , int w_ = INFINITE):s(s_), v(v_),w(w_) { }
}; vector<vector<XEdge> > G(maxn); //图的邻接表 int n, m, maxval[maxn][maxn],map[maxn][maxn];
bool used[maxn][maxn]; void init()
{
int i, a, b, d; memset(used, , sizeof(used));
memset(maxval, , sizeof(maxval));
memset(map, , sizeof(map));
scanf("%d%d", &n, &m);
for (i = ; i < n; i++)
G[i].clear();
for (i = ; i < m; i++)
{
scanf("%d%d%d", &a, &b, &d);
a--;
b--;
G[a].push_back(XEdge(a, b, d));
G[b].push_back(XEdge(b, a, d));
map[a][b] = map[b][a] = d;
}
} bool operator <(const XEdge & e1, const XEdge & e2)
{
return e1.w > e2.w;
} void dp(vector<int> &vUsed, int u, int w)
{
int v, i; for (i = ; i < n; i++)
{
v = i;
maxval[v][u] = _cpp_max(w, maxval[v][u]);
maxval[u][v] = maxval[v][u];
}
} int HeapPrim(const vector<vector<XEdge> > & G)
//G是邻接表,n是顶点数目,返回值是最小生成树权值和
{
int i;
XEdge xDist(,);
priority_queue<XEdge> pq;
vector<int> vDist(n); //各顶点到已经建好的那部分树的距离
vector<int> vUsed(n);//标记顶点是否已经被加入最小生成树
int nDoneNum = ; //已经被加入最小生成树的顶点数目
for( i = ;i < n;i ++ ) {
vUsed[i] = ;
vDist[i] = INFINITE;
}
nDoneNum = ;
int nTotalW = ;
pq.push(XEdge(,,));
while( nDoneNum < n && !pq.empty() ) {
do {
xDist = pq.top(); pq.pop();
} while( vUsed[xDist.v] == && ! pq.empty());
if( vUsed[xDist.v] == ) {
nTotalW += xDist.w;
vUsed[xDist.v] = ;
used[xDist.s][xDist.v] = true;
used[xDist.v][xDist.s] = true;
dp(vUsed, xDist.v, xDist.w);
nDoneNum ++;
for( i = ;i < G[xDist.v].size();i ++ ) {
int k = G[xDist.v][i].v;
if( vUsed[k] == ) {
int w = G[xDist.v][i].w ;
if( vDist[k] > w ) {
vDist[k] = w;
pq.push(XEdge(xDist.v,k,w));
}
}
}
}
}
if( nDoneNum < n )
return -; //图不连通
return nTotalW;
} bool unique()
{
int i, j; for (i = ; i < n; i++)
for (j = i; j < n; j++)
if (map[i][j] && !used[i][j] && maxval[i][j] == map[i][j])
return false;
return true;
} int main()
{
int t, ans;
bool ok; //freopen("t.txt", "r", stdin);
scanf("%d", &t);
while (t--)
{
init();
ans = HeapPrim(G);
ok = unique();
if (ok)
printf("%d\n", ans);
else
printf("Not Unique!\n");
}
return ;
}