模板题
#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=105; const int INF=0x3f3f3f3f; int fa[N],head[N],tot,T,n,m,d[N][N]; struct Edge{ int v,next,w; }edge[N<<1]; 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<<1]; 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=0; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); tot=0; printf("Case #%d : ",++cas); memset(d,0,sizeof(d)); for(int i=1;i<=n;++i)fa[i]=i,head[i]=-1; for(int i=1;i<=m;++i){ scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].w); p[i].mark=0; } sort(p+1,p+1+m); int tmp=n; int mst=0,ans=INF; for(int i=1;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=1; add(p[i].u,p[i].v,p[i].w); add(p[i].v,p[i].u,p[i].w); if(tmp==1)break; } } if(tmp>1){ printf("No way "); continue; } for(int i=1;i<=n;++i){ s=i;dfs(i,0,0); } for(int i=1;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 "); else printf("%d ",ans); } return 0; }