题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1403
题意是有n个点m条边,输入m条边和它的权值,问能否构成最小生成树,如果不能就输出No way,如果能就判断能否构成次小生成树,如果不行就输出No second way,否则就输出次小生成树权值。
思路也就是裸的次小生成树,但是因为这道题会有重边,如果用Prim的话会不太好记录,所以这道题用Kruskal以边来写的话会方便很多。两者思路都一样,都是求出最小生成树的过程中记录边,然后再删边加边。
AC代码:
#include <bits/stdc++.h>
#define maxn 205
#define inf 0x3f3f3f3f
using namespace std;
struct Node{
int x,y,w;
bool operator < (const Node &a) const{
return a.w > w;
}
}Edge[maxn];
int pre[maxn], num;
int used[maxn];
int T,n,m;
int cnt;
void init(){
for(int i=0;i<=n;i++) pre[i] = i;
}
void add(int u,int v,int w){
Edge[num].x = u;
Edge[num].y = v;
Edge[num++].w = w;
}
int Find(int x){
if(x != pre[x]) pre[x] = Find(pre[x]);
return pre[x];
}
void Kruskal(){
sort(Edge, Edge + num);
for(int i=0;i<num;i++){
int fx = Find(Edge[i].x);
int fy = Find(Edge[i].y);
if(fx != fy){
pre[fx] = fy;
used[cnt ++] = i;
}
if(cnt == n - 1) return;
}
}
int main()
{
int Case = 1;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
init();
num = 0;
for(int i=0;i<m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u, v, w);
// add(v, u, w);
}
printf("Case #%d : ",Case++);
cnt = 0;
Kruskal();
if(cnt != n - 1){
puts("No way");
continue;
}
if(m == n - 1){
puts("No second way");
continue;
}
int ans = inf;
for(int i=0;i<cnt;i++){
int sum = 0;
int xx = 0;
init();
for(int j=0;j<num;j++){
if(j == used[i]) continue;
int fx = Find(Edge[j].x);
int fy = Find(Edge[j].y);
if(fx != fy){
pre[fx] = fy;
sum += Edge[j].w;
xx ++;
}
if(xx == n - 1)break;
}
if(xx == n - 1) ans = min(ans, sum);
}
if(ans == inf)puts("No second way");
else printf("%d\n", ans);
}
return 0;
}