http://PRayer.hustoj.com/problem.php?id=1823 CF上好像也有题 这题其实蛮巧妙的 显然暴力的代码也难搞 那我直接说标算了； 吧原图的最小生成树搞出来 对于询问 如果边不在我们求出来的最小生成树上，那一定会形成一个环 我们只要把环里除询问边外最长的边删掉就可以了 妥妥的； 但是证明去找到最长边呢 我第一个反应就是暴力； 后来zyy大佬说用lca 对啊 如果我们把询问边砍掉 就是破环 lac其两个端点，必然会访问其环上的各个边 所以在搞倍增表时，随手搞一个倍增max表就好了
#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#include<cstring>#include<string>#define Ll long longusing namespace std;struct cs{ int x,y,z,num;}a[10001],aa[10001];//读入a,aa备份 int g[1001][1001],deep[1001],bz[1001][15],ma[1001][15];//g来存最小生成树，ma就是倍增max bool b[10001];//表示边i在不在原来的最小生成树里 int father[1001];//我用kruskalint n,m,xx,yy,ans,start;bool cmp(cs a,cs b){ return a.z<b.z;}int getfa(int x){ if(father[x]==x)return x; father[x]=getfa(father[x]); return father[x];}void dfs(int x,int y,int z){ deep[x]=z; bz[x][0]=y; ma[x][0]=g[x][y]; for(int i=1;i<=n;i++) if(g[i][x]>0&&i!=y)dfs(i,x,z+1);}void bzb(){ for(int j=1;(1<<j)<=n;j++) for(int i=1;i<=n;i++){ bz[i][j]=bz[bz[i][j-1]][j-1]; ma[i][j]=max(ma[i][j-1],ma[bz[i][j-1]][j-1]); }}void happytogether(int x,int y){ if(x==y)return; while(1){ int j=0; if(bz[x][j]==bz[y][j]){ xx=max(xx,ma[y][j]); xx=max(xx,ma[x][j]); return; } while(bz[x][j]!=bz[y][j])j++; j--; xx=max(xx,ma[y][j]); xx=max(xx,ma[x][j]); x=bz[x][j]; y=bz[y][j]; }}int upone(int stdd,int x){ while(deep[x]!=stdd){ int j=0; while(deep[bz[x][j]]>=stdd)j++; xx=max(xx,ma[x][j-1]); x=bz[x][j-1]; } return x;}void lca(int x,int y){ if(deep[x]>deep[y])swap(x,y); y=upone(deep[x],y); happytogether(x,y);} main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); a[i].num=i; aa[i].x=a[i].x;aa[i].y=a[i].y;aa[i].z=a[i].z; } sort(a+1,a+m+1,cmp); for(int i=1;i<=n;i++)father[i]=i; for(int i=1;i<=m;i++){ xx=getfa(a[i].x); yy=getfa(a[i].y); if(xx==yy)continue; ans+=a[i].z; father[xx]=yy; b[a[i].num]=1; g[a[i].y][a[i].x]=g[a[i].x][a[i].y]=a[i].z; start=a[i].x; } dfs(start,0,1); bzb(); for(int i=1;i<=m;i++) if(b[i])cout<<ans<<endl;else{ xx=0; lca(aa[i].x,aa[i].y); cout<<ans-xx+aa[i].z<<endl; }}新闻热点
疑难解答
