POJ 1679 The Unique MST(最小生成ツリーが一意か否かを判断)
テーマリンク:kuangbinあなたを連れて飛ぶテーマ6最小生成木K-The Unique MST
に言及
無方向図を与え,最小生成ツリーが一意であるか否かを判断する.
構想
最小生成ツリーを求め、結果を記録し、ツリーの各エッジを順次削除し、最小生成ツリーを求め、最初の結果と同じかどうかを見て、同じであれば一意ではない
コード#コード#
に言及
無方向図を与え,最小生成ツリーが一意であるか否かを判断する.
構想
最小生成ツリーを求め、結果を記録し、ツリーの各エッジを順次削除し、最小生成ツリーを求め、最初の結果と同じかどうかを見て、同じであれば一意ではない
コード#コード#
//
// main.cpp
// demo
//
// Created by shiyi-mac on 16/1/2.
// Copyright © 2016 shiyi-mac. All rights reserved.
//
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
const int N = 109;
const int MAX = 100000000;
int d[N];
int g[N][N];
int fa[N];
pair<int, int> v[N];
int prim(int n, int m, bool f)
{
for(int i=0;i<n;i++)
{
d[i] = g[0][i];
fa[i] = 0;
}
d[0] = -1;
int ans = 0;
for(int i=1;i<n;i++)
{
int min = MAX, mini = -1;
for(int j=0;j<n;j++)
{
if(d[j]!=-1 && d[j]<min)
{
min = d[j];
mini = j;
}
}
if(mini == -1)
return -1;
d[mini] = -1;
if(f)
{
v[i].first = mini;
v[i].second = fa[mini];
}
ans += min;
for(int j=0;j<n;j++)
if(d[j]!=-1 && d[j] > g[mini][j])
{
fa[j] = mini;
d[j] = g[mini][j];
}
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n, m;
memset(g, 0x3f, sizeof(g));
scanf("%d%d",&n, &m);
int a, b, c;
for(int i=0;i<m;i++)
{
scanf("%d%d%d", &a, &b, &c);
g[a-1][b-1] = g[b-1][a-1] = c;
}
int ans = prim(n, m, 1);
for(int i=1;i<n;i++)
{
int t = g[v[i].first][v[i].second];
g[v[i].first][v[i].second]
= g[v[i].second][v[i].first] = MAX;
if(ans == prim(n, m, 0))
{
ans = -1;
break;
}
g[v[i].first][v[i].second]
= g[v[i].second][v[i].first] = t;
}
if(ans == -1)
printf("Not Unique!
");
else
printf("%d
",ans);
}
return 0;
}