本文主要是介绍Minimum spanning tree for each edge CodeForces - 609E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
先求最小生成树的边 这些边的对应值就是生成树的权值 再用这些边建图 对所有非生成树上的边的两点 去掉两者路径上的最长边 然后换为当前边的权值 这个过程求个lca即可
这应该是贪心 最小生成树已经是最优解(克鲁斯卡尔方法中 就是从小边找起 感觉也有贪心的意思) 每换下任何一条边都会增加权重(可能不变) 既然非要换至少一条边 那就只换一条就够了
#include <bits/stdc++.h>
using namespace std;
#define ll long longstruct node1
{int id;int u;int v;ll w;ll ans;
};struct node2
{int v;ll w;int next;
};node1 pre[200010];
node2 edge[400010];
ll maxx[200010][20];
int dp[200010][20];
int first[200010],f[200010],book[200010],deep[200010];
int n,m,num;bool cmpI(node1 n1,node1 n2)
{return n1.w<n2.w;
}bool cmpII(node1 n1,node1 n2)
{return n1.id<n2.id;
}void addedge(int u,int v,ll w)
{edge[num].v=v;edge[num].w=w;edge[num].next=first[u];first[u]=num++;return;
}int getf(int p)
{if(f[p]==p) return p;else{f[p]=getf(f[p]);return f[p];}
}bool unite(int u,int v)
{int fu,fv;fu=getf(u);fv=getf(v);if(fu!=fv){f[fv]=fu;return true;}else return false;
}void dfs(int cur,int pre)
{ll w;int i,v;for(i=first[cur];i!=-1;i=edge[i].next){v=edge[i].v,w=edge[i].w;if(v!=pre){dp[v][0]=cur;maxx[v][0]=w;deep[v]=deep[cur]+1;dfs(v,cur);}}return;
}void solve()
{int i,j;memset(dp,0,sizeof(dp));memset(maxx,0,sizeof(maxx));memset(deep,0,sizeof(deep));dp[1][0]=1;deep[1]=1;dfs(1,-1);for(j=1;(1<<j)<=n;j++){for(i=1;i<=n;i++){dp[i][j]=dp[dp[i][j-1]][j-1];maxx[i][j]=max(maxx[i][j-1],maxx[dp[i][j-1]][j-1]);}}return;
}int getlca(int u,int v)
{int i;if(deep[u]<deep[v]) swap(u,v);for(i=log2(n);i>=0;i--){if(deep[dp[u][i]]>=deep[v]){u=dp[u][i];}}if(u==v) return u;for(i=log2(n);i>=0;i--){if(dp[u][i]!=dp[v][i]){u=dp[u][i];v=dp[v][i];}}return dp[u][0];
}ll getmax(int p,int lca)
{ll res;int i;res=0;for(i=log2(n);i>=0;i--){if(deep[dp[p][i]]>=deep[lca]){res=max(res,maxx[p][i]);p=dp[p][i];}}return res;
}int main()
{ll sum;int i,cnt,lca;while(scanf("%d%d",&n,&m)!=EOF){for(i=1;i<=m;i++){pre[i].id=i;scanf("%d%d%lld",&pre[i].u,&pre[i].v,&pre[i].w);}for(i=1;i<=n;i++){f[i]=i;}memset(book,0,sizeof(book));sort(pre+1,pre+m+1,cmpI);cnt=0,sum=0;for(i=1;i<=m;i++){if(unite(pre[i].u,pre[i].v)){book[i]=1;cnt++,sum+=pre[i].w;}if(cnt==n-1) break;}memset(first,-1,sizeof(first));num=0;for(i=1;i<=m;i++){if(book[i]){addedge(pre[i].u,pre[i].v,pre[i].w);addedge(pre[i].v,pre[i].u,pre[i].w);pre[i].ans=sum;}}solve();for(i=1;i<=m;i++){if(!book[i]){lca=getlca(pre[i].u,pre[i].v);int res=max(getmax(pre[i].v,lca),getmax(pre[i].u,lca));pre[i].ans=sum-res+pre[i].w;}}sort(pre+1,pre+m+1,cmpII);for(i=1;i<=m;i++){printf("%lld\n",pre[i].ans);}}return 0;
}
这篇关于Minimum spanning tree for each edge CodeForces - 609E的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
