CF Educational Codeforces Round 3 E. Minimum spanning tree for each edge 最小生成树变种

题目链接:http://codeforces.com/problemset/problem/609/E

大致就是有一棵树,对于每一条边,询问包含这条边,最小的一个生成树的权值。

做法就是先求一次最小生成树,标记最小生成树上的边,对于这些边,直接就是原始最小生成树。否则必然可以在去掉u到v路径上最长边,再加上边u->v,这一定是包含此边最小的生成树。

查询最长边,可以用树链剖分,也可以树上倍增。

 #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctime>
#include <cassert> using namespace std; const int N=2e5+;
const int INF=0x3f3f3f3f;
struct Node {
int u,v,w;
int id;
bool operator < (const Node &o) const {
return w<o.w;
}
}node[N];
struct Edge{
int to,next,w;
}edge[N<<];
int idx,head[N];
void addedge(int u,int v,int w){
++idx;
edge[idx].to=v;
edge[idx].next=head[u];
edge[idx].w=w;
head[u]=idx;
}
int dep[N];
int par[N][];
int dis[N][];
void dfs(int u,int f,int d){
dep[u]=d;
for (int k=head[u];k;k=edge[k].next){
int v=edge[k].to;
if (v==f) continue;
par[v][]=u;
dis[v][]=edge[k].w;
dfs(v,u,d+);
}
}
int kthA(int u,int k) {
for (int i=;i>=;i--) {
if (k>=(<<i)) {
k-=(<<i);
u=par[u][i];
}
}
return u;
}
int kthD(int u,int k) {
int ret=;
for (int i=;i>=;i--) {
if (k>=(<<i)) {
k-=(<<i);
ret=max(ret,dis[u][i]);
u=par[u][i];
}
}
return ret;
}
void calc(int n) {
for (int i=;i<=;i++) {
int k=<<(i-);
for (int j=;j<=n;j++) {
par[j][i]=par[par[j][i-]][i-];
dis[j][i]=max(dis[j][i-],dis[par[j][i-]][i-]);
}
}
}
int get(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int ret=kthD(u,dep[u]-dep[v]);
u=kthA(u,dep[u]-dep[v]);
if(u==v)return ret;
for(int i=;i>=;i--){
if(par[u][i]==par[v][i])continue;
ret=max(ret,dis[u][i]);
ret=max(ret,dis[v][i]);
u=par[u][i];
v=par[v][i];
}
ret=max(ret,dis[u][]);
ret=max(ret,dis[v][]);
return ret;
}
int fa[N];
int find(int x) {
if (fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
bool mark[N];
long long ret[N];
int main () {
ios_base::sync_with_stdio(false);
int n,m;
while (cin>>n>>m) {
for (int i=;i<=m;i++) {
cin>>node[i].u>>node[i].v>>node[i].w;
node[i].id=i;
mark[i]=false;
}
sort(node+,node++m);
long long sum=;
for (int i=;i<=n;i++)
fa[i]=i;
idx=;memset(head,,sizeof head);
for (int i=;i<=m;i++) {
int u=node[i].u;
int v=node[i].v;
int w=node[i].w;
int id=node[i].id;
int fu=find(u);
int fv=find(v);
if (fu==fv) continue;
fa[fu]=fv;
sum+=w;
mark[id]=true;
addedge(u,v,w);
addedge(v,u,w);
}
dfs(,-,);
calc(n);
for (int i=;i<=m;i++) {
int id=node[i].id;
int u=node[i].u;
int v=node[i].v;
int w=node[i].w;
if (mark[id]) ret[id]=sum;
else {
int mx=get(u,v);
ret[id]=sum+w-mx;
}
}
for (int i=;i<=m;i++)
cout<<ret[i]<<endl;
}
return ;
}
上一篇:ORA-00742:Log read detects lost writein thread 1 sequence 1202 block 137840


下一篇:Autel IM608 All Key Lost Programming for Chevrolet Volt 2015