Educational Codeforces Round 3 E. Minimum spanning tree for each edge LCA/(树链剖分+数据结构) + MST

E. Minimum spanning tree for each edge

 

Connected undirected weighted graph without self-loops and multiple edges is given. Graph contains n vertices and m edges.

For each edge (u, v) find the minimal possible weight of the spanning tree that contains the edge (u, v).

The weight of the spanning tree is the sum of weights of all edges included in spanning tree.

Input
 

First line contains two integers n and m (1 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105) — the number of vertices and edges in graph.

Each of the next m lines contains three integers ui, vi, wi (1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ wi ≤ 109) — the endpoints of the i-th edge and its weight.

Output
 

Print m lines. i-th line should contain the minimal possible weight of the spanning tree that contains i-th edge.

The edges are numbered from 1 to m in order of their appearing in input.

Examples

input
 

5 7
1 2 3
1 3 1
1 4 5
2 3 2
2 5 3
3 4 2
4 5 4

output
 

9
8
11
8
8
8
9

题意：

　　给你n个点，m条边的带权无向图

　　问你分别包含第i条边的 MST 权值 是多少

题解：

　　先求一遍MST，这样知道了 总权值， 和某些 构成 MST 的 边

　　假设 第 i 条边 在 当前求的 MST 的 边中

　　　　那么 答案就是 这个 weight吧

　　假如 第 i 条边 不在 当前 求的 MST 中，那么我们就加入在这个 MST的图中，会发现 无论 如何都构成 环

　　那么 答案 就是 ，在这个环上 删除一条 除了加入的边 的权 值 最大的 那一条边

　　问题就变成了 去MST 中 任意两点 的 边权 最大值

　　这个问题的解法有很多

　　　　我写的是LCA ，复杂度是logn * m

　　　　还可以 直接 暴力 一点的写法

#include<bits/stdc++.h>

using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18;

const double Pi = acos(-1.0);

const int N = 2e5+, M = 5e5+, inf = 2e9, mod = 1e9+;

int fa[N],pa[N][],mx[N][],deep[N],vis[N],n,m;

LL weight;

LL ans[N];

vector<pii> G[N];

struct edge{

        int u,v,w,id;

        bool operator < (const edge &b) const {

            return w<b.w;

        }

}e[M];

int finds(int x) {return x == fa[x] ? x:fa[x]=finds(fa[x]);}

void dfs(int u,int f,int c) {

        pa[u][]=f, mx[u][]=c;

        for(int i = ; i < G[u].size(); ++i) {

            int to = G[u][i].first;

            if(to == f) continue;

            deep[to] = deep[u] + ;

            dfs(to,u,G[u][i].second);

        }

}

void solve() {

        for(int i = ; i <= n; ++i) fa[i] = i;

        sort(e+,e+m+);

        for(int i = ; i <= m; ++i) {

            int fx = finds(e[i].u);

            int fy = finds(e[i].v);

            if(fx == fy) continue;

            G[e[i].u].push_back(MP(e[i].v,e[i].w));

            G[e[i].v].push_back(MP(e[i].u,e[i].w));

            fa[fx] = fy;

            vis[i] = ;

            weight += e[i].w;

        }

        dfs(,-,-);

        for(int k = ; k < ; ++k) {

            for(int i = ; i <= n; ++i) {

                if(pa[i][k-] == -)

                    pa[i][k] = -, mx[i][k] = -;

                else

                    pa[i][k] = pa[pa[i][k-]][k-],

                    mx[i][k] = max(mx[i][k-],mx[pa[i][k-]][k-]);

            }

        }

}

int Lca(int u,int v) {

        if(deep[u] > deep[v]) swap(u,v);

        int ret = ;

        for(int k = ; k < ; ++k)

            if((deep[v] - deep[u])>>k & )

                ret = max(ret, mx[v][k]), v = pa[v][k];

        if(u == v) return ret;

        for(int k = ; k >= ; --k)

        if(pa[u][k] != pa[v][k]) {

            ret = max(ret, mx[u][k]), u = pa[u][k];

            ret = max(ret, mx[v][k]), v = pa[v][k];

        }

        return max(ret, max(ret, max(mx[u][],mx[v][])));

}

int main() {

        scanf("%d%d",&n,&m);

        for(int i = ; i <= m; ++i) {

            scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);

            e[i].id = i;

        }

        solve();

        for(int i = ; i <= m; ++i) {

            if(vis[i]) ans[e[i].id] = weight;

            else {

                ans[e[i].id] = weight - Lca(e[i].u,e[i].v) + e[i].w;

            }

        }

        for(int i = ; i <= m; ++i) printf("%I64d\n",ans[i]);

}

好暴力的写法 %

#include<bits/stdc++.h>

using namespace std;  

#define PB push_back

#define MP make_pair

#define SZ(v) ((int)(v).size())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)

#define REP(i,n) FOR(i,0,n)

#define FORE(i,a,b) for(int i=(a);i<=(b);++i)

#define REPE(i,n) FORE(i,0,n)

#define FORSZ(i,a,v) FOR(i,a,SZ(v))

#define REPSZ(i,v) REP(i,SZ(v))

typedef long long ll;

typedef unsigned long long ull;

ll gcd(ll a,ll b) { return b==?a:gcd(b,a%b); }

const int MAXN=;

const int MAXM=;

typedef struct E { int a,b,c,idx; } E;

bool operator<(const E &p,const E &q) { return p.c<q.c; }

int n,m;

E e[MAXM];

int par[MAXN],sz[MAXN],val[MAXN];

ll ret;

int extra[MAXM];

int process(int a,int b,int c) {

    int mx=;

    while((par[a]!=a||par[b]!=b)&&a!=b) { if(par[b]==b||par[a]!=a&&sz[a]<=sz[b]) mx=max(mx,val[a]),a=par[a]; else mx=max(mx,val[b]),b=par[b]; }

    if(a==b) return c-mx;

    if(sz[a]<sz[b]) swap(a,b);

    sz[a]+=sz[b]; par[b]=a; val[b]=c; ret+=c;

    return ;

}

void run() {

    scanf("%d%d",&n,&m);

    REP(i,m) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c),--e[i].a,--e[i].b,e[i].idx=i;

    sort(e,e+m);

    ret=; REP(i,n) par[i]=i,sz[i]=;

    REP(i,m) extra[e[i].idx]=process(e[i].a,e[i].b,e[i].c);

    REP(i,m) printf("%I64d\n",ret+extra[i]);

}

int main() {

    run();

    return ;

}

Educational Codeforces Round 3 E. Minimum spanning tree for each edge LCA/(树链剖分+数据结构) + MST的相关教程结束。