UVA 10462 Is There A Second Way Left? 次小生成树

模板题

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;
const int N=;
const int INF=0x3f3f3f3f;
int fa[N],head[N],tot,T,n,m,d[N][N];
struct Edge{
int v,next,w;
}edge[N<<];
void add(int u,int v,int w){
edge[tot].v=v;
edge[tot].w=w;
edge[tot].next=head[u];
head[u]=tot++;
}
struct Node{
int u,v,w;
bool mark;
bool operator<(const Node &rhs)const{
return w<rhs.w;
}
}p[N<<];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int s;
void dfs(int u,int f,int t){
d[s][u]=t;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].v;
if(v==f)continue;
dfs(v,u,max(t,edge[i].w));
}
}
int main()
{
int cas=;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
tot=;
printf("Case #%d : ",++cas);
memset(d,,sizeof(d));
for(int i=;i<=n;++i)fa[i]=i,head[i]=-;
for(int i=;i<=m;++i){
scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].w);
p[i].mark=;
}
sort(p+,p++m);
int tmp=n;
int mst=,ans=INF;
for(int i=;i<=m;++i){
int u=find(p[i].u),v=find(p[i].v);
if(u!=v){
--tmp;
fa[u]=v;
mst+=p[i].w;
p[i].mark=;
add(p[i].u,p[i].v,p[i].w);
add(p[i].v,p[i].u,p[i].w);
if(tmp==)break;
}
}
if(tmp>){
printf("No way\n");
continue;
}
for(int i=;i<=n;++i){
s=i;dfs(i,,);
}
for(int i=;i<=m;++i){
if(p[i].mark)continue;
ans=min(ans,mst-d[p[i].u][p[i].v]+p[i].w);
}
if(ans==INF)printf("No second way\n");
else printf("%d\n",ans);
}
return ;
}
上一篇:[Inside HotSpot] C1编译器HIR的构造


下一篇:Liquibase的简单使用