博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
NYOJ 118:修路方案
阅读量:6364 次
发布时间:2019-06-23

本文共 2501 字,大约阅读时间需要 8 分钟。

NYOJ 118:修路方案

题目链接:

次小生成树

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

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

  E[T]={e1,e2,e3,...,en-1},E[T']={f1,f2,f3,...,fn-1}(均按权值从小到大排列)

假设ei≠ej,fi≠fj(对结果不影响)。设ek和fk为第一个使ek≠fk的下标,显然(由Kruskal算法加边的顺序)可以得到ek<fk.

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

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

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

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

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


 

 

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

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

 

这道题采用添边去边的方法,基于Prim实现,时间复杂度为O(V2+E).

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

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

代码如下:

1 #include 
2 #include
3 #include
4 #include
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
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
>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
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
-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\n";89 else cout<<"No\n";90 }91 }

 

转载于:https://www.cnblogs.com/barrier/p/6417236.html

你可能感兴趣的文章
Mysql索引的类型
查看>>
Eclipse debug模式 总是进入processWorkerExit
查看>>
ELK+Filebeat+Kafka+ZooKeeper 构建海量日志分析平台
查看>>
Nginx的https配置记录以及http强制跳转到https的方法梳理
查看>>
[每天五分钟,备战架构师-1]操作系统的类型和结构
查看>>
springcloud(十三):Eureka 2.X 停止开发,但注册中心还有更多选择:Consul 使用详解...
查看>>
关于Boolean类型做为同步锁异常问题
查看>>
TestLink运行环境:Redhat5+Apache2.2.17+php-5.3.5+MySQL5.5.9-1
查看>>
Get File Name from File Path in Python | Code Comments
查看>>
显示本月每一天日期
查看>>
Open Source Databases Comparison
查看>>
sprintf,你知道多少?
查看>>
[转]java 自动装箱与拆箱
查看>>
NET的堆和栈04,对托管和非托管资源的垃圾回收以及内存分配
查看>>
think in coding
查看>>
IdHttpServer实现webservice
查看>>
HTML的音频和视频
查看>>
Linux大文件已删除,但df查看已使用的空间并未减少解决
查看>>
iOS - App 应用
查看>>
Unsupported major.minor version 52.0
查看>>