题目:
kruscal别忘了先按边权sort。自己觉得那部分处理得还挺好的。(联想到之前某题的经验)
没管重边。好像还行?
#include#include #include #include #include #define ll long longusing namespace std;const int N=1e5+5,M=3e5+5,Lm=20,INF=1e9+7;int n,m,head[N],xnt=1,pre[N][Lm+5],mx[N][Lm+5][2];int fa[N],dis[N],fr[N],dep[N];ll ans,zl;bool vis[N],use[M<<1];struct Ed{ int next,fr,to,w,bh; Ed(int n=0,int f=0,int t=0,int w=0):next(n),fr(f),to(t),w(w) {} bool operator< (const Ed &b)const { return bh <<1];void add(int x,int y,int z){ ed[++xnt]=Ed(head[x],x,y,z);head[x]=xnt;ed[xnt].bh=xnt; ed[++xnt]=Ed(head[y],y,x,z);head[y]=xnt;ed[xnt].bh=xnt;}int find(int a){ return fa[a]==a?a:fa[a]=find(fa[a]);}bool cmp(Ed u,Ed v){ return u.w =0;i--) if(dep[pre[x][i]]>=dep[y]) cz(w0,w1,x,i),x=pre[x][i]; if(x==y)return; for(int i=Lm;i>=0;i--) if(pre[x][i]!=pre[y][i]) { cz(w0,w1,x,i);cz(w0,w1,y,i); x=pre[x][i];y=pre[y][i]; } if(x!=y) { cz(w0,w1,x,0);cz(w0,w1,y,0); x=pre[x][0];y=pre[y][0]; }}int main(){ scanf("%d%d",&n,&m);int x,y,z; for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z);add(x,y,z); } kruscal(); dfs(1,0);zl=INF; for(int i=2;i<=xnt;i+=2) if(!use[i]) { int w0=-1,w1=-1; solve(ed[i].fr,ed[i].to,w0,w1); if(ed[i].w>w0)zl=min(zl,(ll)ed[i].w-w0); else if(ed[i].w>w1)zl=min(zl,(ll)ed[i].w-w1); } printf("%lld",ans+zl); return 0;}