E. Minimum spanning tree for each edge

题目连接：

http://www.codeforces.com/contest/609/problem/E

Description

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.

Sample Input

5 7

1 2 3

1 3 1

1 4 5

2 3 2

2 5 3

3 4 2

4 5 4

Sample Output

Hint

题意

给你一个图，n点m边。对于每个边，问你包含这条边的最小生成树是多少。

题解：

先求最小生成树..查询在树上的边不影响结果,不在树上的边加入会产生环,那么求出这个环上权最大的边,删掉就是包含当前边的最小生成树.这个查询可以用倍增lca做

当然，直接上熟练剖分/LCT也是兹瓷的！

代码

#include<bits/stdc++.h>

using namespace std;

const int N=200500;

int n,m;

struct node

{

    int x,y,c,no;

}E[N<<1];

int pre[N],to[N<<1],w[N<<1],nxt[N<<1];

int fa[N],lca[N][22],p[N][22],dep[N],cnt;

long long ans[N];

void makeedge(int x,int y,int c)

{

    to[cnt]=x;w[cnt]=c;nxt[cnt]=pre[y];pre[y]=cnt++;

    to[cnt]=y;w[cnt]=c;nxt[cnt]=pre[x];pre[x]=cnt++;

}

int getfather(int x)

{

    if(fa[x]==x) return fa[x];else return fa[x]=getfather(fa[x]);

}

void dfs(int x)

{

    for(int it=pre[x];~it;it=nxt[it])

    {

        int y=to[it],c=w[it];

        if(y==lca[x][0]) continue;

        dep[y]=dep[x]+1,lca[y][0]=x,p[y][0]=c;

        dfs(y);

    }

}

int query(int x,int y)

{

    int ret=0;

    if(dep[x]<dep[y]) swap(x,y);

    for(int i=21;i>=0;i--)

        if(dep[x]-(1<<i)>=dep[y])

            ret=max(ret,p[x][i]),x=lca[x][i];

    if(x==y) return ret;

    for(int i=21;i>=0;i--)

        if(lca[x][i]!=lca[y][i])

            ret=max(ret,max(p[x][i],p[y][i])),x=lca[x][i],y=lca[y][i];

    ret=max(ret,max(p[y][0],p[x][0]));

    return ret;

}

bool cmp(node t1,node t2)

{

    return t1.c<t2.c;

}

int main()

{

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

    memset(pre,-1,sizeof(pre));

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

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

    {

        scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].c);

        E[i].no=i;

    }

    sort(E+1,E+m+1,cmp);

    long long tot=0;

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

    {

        int x=E[i].x,y=E[i].y;

        int f1=getfather(x),f2=getfather(y);

        if(f1!=f2)

        {

            fa[f2]=f1;

            tot+=(long long)E[i].c;

            makeedge(x,y,E[i].c);

        }

    }

    dfs(1);

    for(int j=1;j<=21;j++)

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

            if(lca[i][j-1])

            {

                lca[i][j]=lca[lca[i][j-1]][j-1];

                p[i][j]=max(p[i][j-1],p[lca[i][j-1]][j-1]);

            }

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

    {

        int x=E[i].x,y=E[i].y;

        int tt=query(x,y);

        ans[E[i].no]=max(0LL,(long long)E[i].c-(long long)tt)+tot;

    }

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

        printf("%I64d\n",ans[i]);

    return 0;

}

秒客网

Codeforces Educational Codeforces Round 3 E. Minimum spanning tree for each edge LCA链上最大值