題目鏈接：點擊查看

題目大意：給出一張 n 個點和 m 條邊組成的無向圖，現(xiàn)在詢問包含每一條邊的最小生成樹

題目分析：考慮求解次小生成樹的思路：

求出最小生成樹 ans

枚舉每一條非樹邊 ( u , v )，然后刪除樹上 ( u , v ) 這條路徑上的最大值，即此時生成樹的答案變?yōu)?ans +?w( u , v ) - mmax

選擇次小的作為答案

所以在求出最小生成樹后，對于每一條邊來說，只需要求出路徑上邊權(quán)的最大值即可

可以用樹剖+線段樹硬寫，因為本題是靜態(tài)的一棵樹，所以用樹上倍增在時間復(fù)雜度以及代碼復(fù)雜度上顯得更加優(yōu)秀一些（都是當(dāng)一個快樂的碼農(nóng)）

代碼：

樹鏈剖分+線段樹

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;struct Edge {int u,v,id;LL w;void input(int i){id=i;scanf("%d%d%lld",&u,&v,&w);}bool operator<(const Edge& t)const{return w<t.w;} }edge[N];vector<pair<int,int>>node[N];int f[N],n,m;LL sum=0,ans[N];int find(int x) {return f[x]==x?x:f[x]=find(f[x]); }bool merge(int x,int y) {int xx=find(x),yy=find(y);if(xx==yy)return false;f[xx]=yy;return true; }void addedge(int u,int v,int w) {node[u].emplace_back(v,w);node[v].emplace_back(u,w); }void Kruskal() {for(int i=1;i<=n;i++)f[i]=i;sort(edge+1,edge+1+m);for(int i=1;i<=m;i++)if(merge(edge[i].u,edge[i].v)){sum+=edge[i].w;addedge(edge[i].u,edge[i].v,edge[i].w);} }int fa[N],deep[N],num[N],son[N],val[N];void dfs1(int u,int f,int dep) {deep[u]=dep;num[u]=1;son[u]=-1;fa[u]=f;for(auto it:node[u]){int v=it.first,w=it.second;if(v==f)continue;val[v]=w;dfs1(v,u,dep+1);num[u]+=num[v];if(son[u]==-1||num[son[u]]<num[v])son[u]=v;} }int top[N],id[N],idd[N],cnt;void dfs2(int u,int fa,int root) {top[u]=root;id[u]=++cnt;idd[cnt]=u;if(son[u]!=-1)dfs2(son[u],u,root);for(auto it:node[u]){int v=it.first,w=it.second;if(v==fa||v==son[u])continue;dfs2(v,u,v);} }struct Node {int l,r,mmax; }tree[N<<2];void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;if(l==r){tree[k].mmax=val[idd[l]];return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax); }int query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l)return 0;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].mmax;return max(query(k<<1,l,r),query(k<<1|1,l,r)); }int query(int x,int y) {int mmax=0;while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]])swap(x,y);mmax=max(mmax,query(1,id[top[x]],id[x]));x=fa[top[x]];}if(x==y)return mmax;if(deep[x]>deep[y])swap(x,y);mmax=max(mmax,query(1,id[x]+1,id[y]));return mmax; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)edge[i].input(i);Kruskal();dfs1(1,0,0);dfs2(1,0,1);build(1,1,n);for(int i=1;i<=m;i++)ans[edge[i].id]=sum+edge[i].w-query(edge[i].u,edge[i].v);for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);return 0; }

樹上倍增：

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;struct Edge {int u,v,id;LL w;void input(int i){id=i;scanf("%d%d%lld",&u,&v,&w);}bool operator<(const Edge& t)const{return w<t.w;} }edge[N];vector<pair<int,int>>node[N];int f[N],n,m;LL sum=0,ans[N];int find(int x) {return f[x]==x?x:f[x]=find(f[x]); }bool merge(int x,int y) {int xx=find(x),yy=find(y);if(xx==yy)return false;f[xx]=yy;return true; }void addedge(int u,int v,int w) {node[u].emplace_back(v,w);node[v].emplace_back(u,w); }void Kruskal() {for(int i=1;i<=n;i++)f[i]=i;sort(edge+1,edge+1+m);for(int i=1;i<=m;i++)if(merge(edge[i].u,edge[i].v)){sum+=edge[i].w;addedge(edge[i].u,edge[i].v,edge[i].w);} }int dp[N][20],mmax[N][20],deep[N];void dfs(int u,int fa,int dep,int w) {deep[u]=dep;dp[u][0]=fa;mmax[u][0]=w;for(int i=1;i<20;i++){dp[u][i]=dp[dp[u][i-1]][i-1];mmax[u][i]=max(mmax[u][i-1],mmax[dp[u][i-1]][i-1]);}for(auto it:node[u]){int v=it.first,w=it.second;if(v==fa)continue;dfs(v,u,dep+1,w);} }int query(int x,int y) {int ans=0;if(deep[x]<deep[y])swap(x,y);for(int i=19;i>=0;i--)if(deep[x]-deep[y]>=(1<<i)){ans=max(ans,mmax[x][i]);x=dp[x][i];}if(x==y)return ans;for(int i=19;i>=0;i--)if(dp[x][i]!=dp[y][i]){ans=max(ans,mmax[x][i]);ans=max(ans,mmax[y][i]);x=dp[x][i];y=dp[y][i];}ans=max(ans,mmax[x][0]);ans=max(ans,mmax[y][0]);return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)edge[i].input(i);Kruskal();dfs(1,0,0,0);for(int i=1;i<=m;i++)ans[edge[i].id]=sum+edge[i].w-query(edge[i].u,edge[i].v);for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);return 0; }

?

超強干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 609E Minimum spanning tree for each edge(最小生成树+树链剖分+线段树/树上倍增)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。