严格次小生成树
2020-03-08 16:00:49来源:博客园 阅读 ()
严格次小生成树
题目描述
小C最近学了很多最小生成树的算法,Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时,小P又来泼小C冷水了。小P说,让小C求出一个无向图的次小生成树,而且这个次小生成树还得是严格次小的。
这下小 C 蒙了,他找到了你,希望你帮他解决这个问题。
输入格式
第一行包含两个整数N 和M,表示无向图的点数与边数。 接下来 M行,每行 3个数x y z 表示,点 x 和点y之间有一条边,边的权值为z。
输出格式
包含一行,仅一个数,表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)
洛谷P4180
分析:看到这个题的第一眼想到的是枚举,把所有生成树枚举一遍求最小的,但是显然不行,因为数据有些大了。
想一下最小生成树的算法?Kurskal是通过每一次加最小边来实现最小树,所以我们考虑一下边。
对于一棵最小生成树而言,删去树上一边,再加上一条边维护树,就有可能构成次小生成树,为保证它是严格的,所以还要再判断这条边与删去的边是否相等。
现在我们考虑删边,如何保证删去边再加上边仍然是树呢?显然先加边,然后看这条边与其他边构成的环中,最大的那条边是多少,为什么要用最大边呢,因为要求的是次小生成树,在一个点附近,加完边后剩下的边一定大于等于加上的边,不然根据Kurskal不会把这条边加上,但这条边还有可能和加的边相等,所以在记录最大边的同时还要记录次大边。
删边和加边的问题解决了,接下来就是记录了,关于记录,使用lca是我没有想到的。
为什么要用lca呢?加边后构成的环,不考虑加的这条边的话,可以分成两部分,一是从边的from到lca,二是从边的to到lca,所以在跑倍增lca的同时(顺便)维护一下最大值和次大值。
最后就是计算了,计算的时候也是同上分两部分,记得判断最大值是不是和边权一样,如果是的话要用次大值。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10; //前向星存边 struct Edge{ int to,from,next,val; bool isin; Edge(){isin=val=next=0;} bool operator < (const Edge &A)const { return val<A.val; } }e[N<<1],E[N*3]; int len,Head[N]; void Ins(int a,int b,int c){ e[++len].to=b;e[len].val=c; e[len].next=Head[a];Head[a]=len; } //并查集+Kurskal int f[N],m,n; int find(int x){ return f[x]==x?x:(f[x]=find(f[x])); } int ans=0x3f3f3f3f;long long tot=0; void Krs(){ int cnt=1; sort(E+1,E+m+1); for(int i=1;cnt<n;i++){ int v=E[i].to,u=E[i].from; if(find(v)!=find(u)){ cnt++; E[i].isin=1; tot+=E[i].val;//计算最小生成树 Ins(u,v,E[i].val); Ins(v,u,E[i].val); f[find(v)]=find(u); } } } //倍增lca板子 int dep[N],p[N][20],Max[N][20],Smax[N][20]; void dfs(int x){ for(int i=0;p[x][i];i++){ p[x][i+1]=p[p[x][i]][i]; Max[x][i+1]=max(Max[x][i],Max[p[x][i]][i]); //注意求次大的时候看看两段的最大值是不是相等,如果不判断的话 //在最大值相等的时候,次大值会被更新为最大值 if(Max[x][i]==Max[p[x][i]][i]) Smax[x][i+1]=max(Smax[x][i],Smax[p[x][i]][i]); else Smax[x][i+1]=max(min(Max[x][i],Max[p[x][i]][i]), max(Smax[x][i],Smax[p[x][i]][i])); } for(int i=Head[x];i;i=e[i].next){ int v=e[i].to; if(v!=p[x][0]){ dep[v]=dep[x]+1; Max[v][0]=e[i].val; Smax[v][0]=-1; p[v][0]=x; dfs(v); } } } //这段和lca板子一模一样 int lca(int a,int b){ if(dep[a]<dep[b])swap(a,b); int d=dep[a]-dep[b]; for(int i=0;d;i++,d>>=1) if(d&1)a=p[a][i]; if(a==b)return a; for(int i=18;i>=0;i--) if(p[a][i]!=p[b][i]) a=p[a][i],b=p[b][i]; return p[a][0]; } //计算 void calc(int u,int v,int w){ int d=dep[u]-dep[v];//深度差,判断路径 int m1=0,m2=0; for(int i=0;d;i++,d>>=1){ if(d&1){//如果可以往上跳 m2=max(m2,Smax[u][i]);//细节,先求次大值 if(Max[u][i]>m1){//如果更新最大值,那么原来的最大值m1可能为新的次大值 m2=max(m2,m1);//判断次大值是否更新 m1=Max[u][i];//更新最大值 } } } if(m1==w)ans=min(ans,w-m2);//如果最大值与边相等,用次大值更新 else ans=min(ans,w-m1);//否则用最大值 } int main(){ // freopen("a.txt","r",stdin); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++) scanf("%d%d%d",&E[i].from,&E[i].to,&E[i].val); Krs(); dfs(1); for(int i=1;i<=m;i++){ if(!E[i].isin){ int u=E[i].from,v=E[i].to,Lca; Lca=lca(u,v); calc(u,Lca,E[i].val); calc(v,Lca,E[i].val); } } printf("%lld\n",tot+ans); }
原文链接:https://www.cnblogs.com/anyixing-fly/p/12411799.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:结题报告
下一篇:关于有趣的windows.h
- 复习C++语法--基础篇 2020-05-27
- C++生成随机数 2020-04-18
- 括号生成 2020-04-09
- 迷宫算法 之 迷宫生成和迷宫寻路 2020-03-25
- CTF中特别小的EXE是怎么生成的 2020-03-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash