原题链接

考察:次小生成树

思路:

        yysy,切模板题很爽,但是莫得进步555

        时间复杂度:O(T*(mlog₂m+n²+m))

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int N = 110,M = 210,INF = 0x3f3f3f3f;
 6 int n,m,h[N],p[N],idx;
 7 int dist[N][N];
 8 struct Path{
 9     int u,v,w;
10     bool vis;
11     bool operator<(Path x){
12         return this->w<x.w;
13     }
14 }path[M];
15 struct Road{
16     int fr,to,ne,w;
17 }road[M<<1];
18 void add(int a,int b,int c)
19 {
20     road[idx].w =c,road[idx].fr = a,road[idx].to = b,road[idx].ne = h[a],h[a] = idx++;
21 }
22 int findf(int x)
23 {
24     if(p[x]!=x) p[x] = findf(p[x]);
25     return p[x];
26 }
27 void dfs(int u,int fa,int max1,int gr)
28 {
29     dist[gr][u] = max1;
30     for(int i=h[u];~i;i=road[i].ne)
31     {
32         int v = road[i].to;
33         if(v==fa) continue;
34         int w = road[i].w;
35         dfs(v,u,max(w,max1),gr);
36     }
37 }
38 int main()
39 {
40     int T,kcase = 0;
41     scanf("%d",&T);
42     while(T--)
43     {
44         scanf("%d%d",&n,&m);
45         int sum = 0,cnt = 0,ans = 0x3f3f3f3f;
46         idx = 0;
47         for(int i=1;i<=n;i++) h[i] = -1,p[i] = i;
48         memset(dist,0,sizeof dist);
49         for(int i=1;i<=m;i++)
50         {
51             int u,v,w; scanf("%d%d%d",&u,&v,&w);
52             path[i] = {u,v,w,0};
53         }
54         sort(path+1,path+m+1);
55         for(int i=1;i<=m;i++) 
56         {
57             int pa = findf(path[i].u),pb = findf(path[i].v);
58             if(pa==pb) continue;
59             sum+=path[i].w;
60             p[pa] = pb;
61             cnt++;
62             path[i].vis = 1;
63             add(path[i].u,path[i].v,path[i].w);
64             add(path[i].v,path[i].u,path[i].w);
65         }
66         if(cnt!=n-1) {printf("Case #%d : No way\n",++kcase);continue;}
67         for(int i=1;i<=n;i++) dfs(i,-1,0,i);
68         for(int i=1;i<=m;i++)
69           if(!path[i].vis)
70           {
71               int u = path[i].u,v =path[i].v; 
72                ans = min(ans,sum-dist[u][v]+path[i].w);
73           }
74         if(ans==INF) printf("Case #%d : No second way\n",++kcase);
75         else printf("Case #%d : %d\n",++kcase,ans);
76     }
77     return 0;
78 }