NYOJ 118：修路方案

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=118

次小生成树

定理：次小生成树和最小生成树有且仅有一条不同边。

证明如下：设T，T'分别是原图的最小生成树和次小生成树，且边集

　　E[T]={e₁,e₂,e₃,...,e_n-1},E[T']={f₁,f₂,f₃,...,f_n-1}（均按权值从小到大排列）

假设e_i≠e_j，f_i≠f_j（对结果不影响）。设e_k和f_k为第一个使e_k≠f_k的下标，显然（由Kruskal算法加边的顺序）可以得到e_k<f_k.

将边e_k添加到次小生成树T'中，形成一个新的子图G=T'U{e_k}，设C为G中的环.

显然E[C]中有且仅有一条比e_k大的边：

假设E[C]中没有比e_k大的边，e_k即为E[C]中最大边，则边和sum[C-{e_k}]≤sum[E[T]∩{e(i,j) for i,j in V[C]}]，这与T为最小生成树矛盾；
假设E[C]中有m（m≥2）条比e_k大的边f_i，那么用e_k替换f_i则可构造出m个不同的比次小生成树小的生成树，这与权值比w[T']小的只有唯一一颗T矛盾.

假设e_t和f_t为第二个使e_t≠f_t的下标，同理得T'U{e_t}的环中有且仅有一条比e_t大的边，然而依次用e_k或e_t替换对应环内的较大值可构造出多个不同的比次小生成树小的生成树，这与T'是次小生成树矛盾.

综上所述，次小生成树和最小生成树有且仅有一条不同边。

有了上述定理，我们可以想到两种构造次小生成树的方法：

求出最小生成树T后，删去E[T]中的边并标记，计算除标记边后的最小生成树；
求出最小生成树T后，添加E[G]-E[T]中的边形成环，删去环内最大的边.

这道题采用添边去边的方法，基于Prim实现，时间复杂度为O（V²+E）.

其中用maxl[i][j]维护最小生成树中结点i到结点j间的最大边，以实现一次添边去边的复杂度O（1）.

为了避免重边的情况，选择的数据结构为邻接链表，并用vise[2*M]标记E[T]。

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <vector>
 4 #include <cstring>
 5 #define pb(x) push_back(x)
 6 #define N 505
 7 #define M 200005
 8 using namespace std;
 9 typedef long long ll;
10 int inf=0x0fffffff;
11 int T,V,E,v,u,w,pre[N],visv[N],vise[2*M],maxl[N][N];
12 struct edge{
13     int to,w,id;
14     edge(int _to=-1,int _w=-1,int _id=-1){
15         to=_to;w=_w;id=_id;
16     }
17 };
18 struct node{
19     int d,id;
20 }dis[N];
21 vector<edge>e[N];
22 void init(){
23     cin>>V>>E;
24     for(int i=1;i<=V;++i){
25         e[i].clear();
26         visv[i]=0;
27         pre[i]=1;
28         dis[i].d=inf;
29         dis[i].id=-1;
30         for(int j=1;j<=V;++j)
31             maxl[i][j]=-inf;
32     }
33     for(int i=0;i<E;++i){
34         cin>>u>>v>>w;
35         e[u].pb(edge(v,w,i));
36         e[v].pb(edge(u,w,i+E));
37         vise[i]=vise[i+E]=0;
38     }
39     for(int i=0;i<(int)e[1].size();++i){
40         int to=e[1][i].to;
41         int w=e[1][i].w;
42         int id=e[1][i].id;
43         if(dis[to].d>w){
44             pre[to]=1;
45             dis[to].d=w;
46             dis[to].id=id;
47         }
48     }
49     visv[1]=1;
50 }
51 bool prim(){
52     for(int t=1;t<V;++t){
53         int k,minn=inf;
54         for(int i=1;i<=V;++i)
55             if(!visv[i]&&minn>dis[i].d)
56                 minn=dis[k=i].d;
57         visv[k]=1;
58         vise[dis[k].id]=vise[dis[k].id+(dis[k].id>=E?-E:E)]=1;
59         int p=pre[k];
60         maxl[k][p]=maxl[p][k]=dis[k].d;
61         for(int i=1;i<=V;++i)
62             if(visv[i])
63                 maxl[k][i]=maxl[i][k]=max(maxl[i][p],maxl[p][k]);
64         for(int i=0;i<(int)e[k].size();++i){
65             int w=e[k][i].w,to=e[k][i].to;
66             if(w<dis[to].d){
67                 dis[to].d=w;
68                 dis[to].id=e[k][i].id;
69                 pre[to]=k;
70             }
71         }
72     }
73     for(int i=1;i<=V;++i){
74         for(int j=0;j<(int)e[i].size();++j){
75             int to=e[i][j].to,w=e[i][j].w,id=e[i][j].id;
76             if(!vise[id])
77                 if(maxl[i][to]>-inf&&maxl[i][to]==w)
78                     return 1;
79         }
80     }
81     return 0;
82 }
83 int main(void){
84     std::ios::sync_with_stdio(false);
85     cin>>T;
86     while(T--){
87         init();
88         if(prim())cout<<"Yes
";
89         else cout<<"No
";
90     }
91 }