bzoj1977 [BeiJing2010组队]次小生成树 Tree

bzoj1977 [BeiJing2010组队]次小生成树 Tree

​​ Description

小 C 最近学了很多最小生成树的算法，Prim 算法、Kurskal 算法、消圈算法等等。 正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说： 如果最小生成树选择的边集是 EM，严格次小生成树选择的边集是 ES，那么需要满足：(value(e) 表示边 e的权值) 这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。

Input

第一行包含两个整数N 和M，表示无向图的点数与边数。 接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。

Output

包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

Sample Input

5 6 1 2 1 1 3 2 2 4 3 3 5 4 3 4 3 4 5 6 Sample Output

11 HINT

数据中无向图无自环； 50% 的数据N≤2 000 M≤3 000； 80% 的数据N≤50 000 M≤100 000； 100% 的数据N≤100 000 M≤300 000 ，边权值非负且不超过 10^9 。

和vijos新年游戏 还有货车运输算是师出同门吧 建议先学习学习次小生成树

这个就是绝对的次小生成树 维护的多点，比较恶心而已

如果我的最大值等于新的边权 那么我就用次大值来计算就好啦

#include#include#define M 330000#define N 110000using namespace std;inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}struct node{ int x,y,z,next;}data1[M],data[N<<1];inline bool cmp(node a,node b){return a.zst1[y][j-1]) st2[y][j]=max(st1[y][j-1],max(st2[fa[y][j-1]][j-1],st2[y][j-1])); else st2[y][j]=max(st1[fa[y][j-1]][j-1],max(st2[fa[y][j-1]][j-1],st2[y][j-1])); } }dfs(y); }}int max1,max2;void lca(int x,int y){ if (dep[x]!=dep[y]){ if (dep[x]max1){ max2=max1;max1=st1[x][i]; } }max2=max(max2,st2[x][i]);x=fa[x][i]; } } if (x==y) return; for (int j=19;j>=0;--j){ if (fa[x][j]!=fa[y][j]){ if (st1[x][j]>max1) max2=max1,max1=st1[x][j];else if(st1[x][j]>max2) max2=st1[x][j]; if (st1[y][j]>max1) max2=max1,max1=st1[y][j];else if(st1[y][j]>max2) max2=st1[y][j]; max2=max(max2,max(st2[x][j],st2[y][j])); x=fa[x][j];y=fa[y][j]; } } if (st1[x][0]>max1) max2=max1,max1=st1[x][0];else if(st1[x][0]>max2) max2=st1[x][0]; if (st1[y][0]>max1) max2=max1,max1=st1[y][0];else if(st1[y][0]>max2) max2=st1[y][0]; max2=max(max2,max(st2[x][0],st2[y][0]));} int main(){ freopen("bzoj1977.in","r",stdin); n=read();m=read(); for (int i=1;i<=m;++i){ int x=read(),y=read(),z=read(); data1[i].x=x;data1[i].y=y;data1[i].z=z; } sort(data1+1,data1+m+1,cmp); for (int i=1;i<=n;++i) fa1[i]=i;long long ans=0,ans1=1LL<<60;Log[0]=-1; for (int i=1;i<=n;++i) Log[i]=Log[i>>1]+1;int cnt=0; for (int i=1;i<=m;++i){ int x=data1[i].x,y=data1[i].y,z=data1[i].z; int xx=find(x),yy=find(y); if (xx!=yy){ans+=z;visit[i]=true; cnt++;data[++num].y=y;data[num].next=h[x];h[x]=num;data[num].z=z; data[++num].y=x;data[num].next=h[y];h[y]=num;data[num].z=z;fa1[xx]=yy; if (cnt==n-1) break; } } dfs(1); for (int i=1;i<=m;++i){ if (!visit[i]){ int x=data1[i].x,y=data1[i].y,z=data1[i].z; max1=max2=0;lca(x,y); if (max1!=z) ans1=min(ans1,(long long)z-max1);else ans1=min(ans1,(long long)z-max2); } } printf("%lld",ans+ans1); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。