http://PRayer.hustoj.com/problem.php?id=1823 CF上好像也有題 這題其實蠻巧妙的 顯然暴力的代碼也難搞 那我直接說標算了； 吧原圖的最小生成樹搞出來 對于詢問 如果邊不在我們求出來的最小生成樹上，那一定會形成一個環(huán) 我們只要把環(huán)里除詢問邊外最長的邊刪掉就可以了 妥妥的； 但是證明去找到最長邊呢 我第一個反應就是暴力； 后來zyy大佬說用lca 對啊 如果我們把詢問邊砍掉 就是破環(huán) lac其兩個端點，必然會訪問其環(huán)上的各個邊 所以在搞倍增表時，隨手搞一個倍增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; }}新聞熱點
疑難解答
