首页 > 代码库 > BZOJ 3124 直径
BZOJ 3124 直径
计算去掉每一条边之后的直径。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxv 200500#define maxe 400500using namespace std;struct edge{ long long v,w,mx,nxt;}e[maxe];int t,n,x,y,z,g[maxv],nume=1,root;int fath_e[maxv],son[maxv],pos;long long val1[maxv],val2[maxv],ans=0,dis[maxv],ret=0,dr=0;inline int read(){ int data=http://www.mamicode.com/0;char ch; while (ch<‘0‘ || ch>‘9‘) ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) { data=data*10+ch-‘0‘; ch=getchar(); } return data;}inline void reset1(){ memset(g+1,0,n*sizeof(int)); ans=0;nume=1;ret=0;}inline void reset2(){ memset(son+1,0,n*sizeof(int));}inline void addedge(int u,int v,int w){ e[++nume].v=v; e[nume].w=w; e[nume].mx=0; e[nume].nxt=g[u]; g[u]=nume;}void dfs1(int x,int fath){ for (int i=g[x];i;i=e[i].nxt) { int v=e[i].v; if (v!=fath) { dis[v]=dis[x]+e[i].w; if (dis[v]>ret) {ret=dis[v];root=v;} dfs1(v,x); } }}void dfs2(int x,int fath){ val1[x]=val2[x]=0;long long fx=0,sx=0; for (int i=g[x];i;i=e[i].nxt) { int v=e[i].v; if (v!=fath) { dis[v]=dis[x]+e[i].w;fath_e[v]=i; dfs2(v,x); if (val2[v]+e[i].w>fx) {sx=fx;fx=val2[v]+e[i].w;son[x]=v;} else if (val2[v]+e[i].w>sx) sx=val2[v]+e[i].w; val1[x]=max(val1[x],val1[v]); } } val2[x]=fx; val1[x]=max(val1[x],fx+sx);}inline void get_labled(int type){ int now=son[root];long long regis=0; while (now) { e[fath_e[now]].mx=max(e[fath_e[now]].mx,val1[now]); e[fath_e[now]^1].mx=max(e[fath_e[now]^1].mx,val1[now]); if (type==2) if (e[fath_e[now]].mx!=dr) ans++; ret++;pos=now;now=son[now]; }}inline void work(){ reset1(); n=read(); for (register int i=1;i<=n-1;i++) { x=read();y=read();z=read(); addedge(x,y,z);addedge(y,x,z); } ret=0; dfs1(1,1); reset2();dis[root]=0;fath_e[root]=0; dfs2(root,root); ret=0;dr=val1[root]; get_labled(1); reset2();root=pos;dis[root]=0;fath_e[root]=0; dfs2(root,root); get_labled(2); printf("%lld\n%lld\n",dr,ans);}int main(){ work(); return 0;}
BZOJ 3124 直径
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。