CF609E Minimum spanning tree for each edge 题解【贪心】【倍增】【LCA】【生成树】

点击量：218

    贪心一定要贪对，最好多找反例试着推翻自己。

目录

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 \le n \le 2\cdot 10^5, n-1 \le m \le 2\cdot 10^5)$ — the number of vertices and edges in graph.

 

Each of the next $ m$ lines contains three integers $ u_i, v_i, w_i (1 \le u_i, v_i \le n, u_i\ne v_i, 1 \le w_i \le 10^9)$ — 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\le 2\times 10^5$，求出过每条边的最小生成树权值。

题解：

    看到这个题首先想到的是边有可能在最小生成树上，也有可能不在，而在树上的最多只有$ n-1$条边，因此如果对剩下的$ m-n+1$条边都做一遍最小生成树的话，$ m\log m$的复杂度肯定承受不了。

    如果要在$ O(n)$或$ O(n\log n)$的时间复杂度内找到每条边的最小生成树，就得利用原本的最小生成树。如果所求边在最小生成树上，就直接输出最小生成树权值。而不在最小生成树上的边又如何处理呢？

    对于这样一棵最小生成树来说，1,2,3成了环，因此在环上，我们必须删掉一条边。

    图中虚线表示被删掉的边。这样一来如果查询①③，就输出原最小生成树答案，如果查询⑥⑦，就把最小生成树答案加上⑥-⑦再减去1-2-6-7-3-1这个环上的最大值。这样贪心就完成了。

    因此我们只需要在以1为根的这个最小生成树中跳倍增就知道环上的最大值是多少辣。

    注意开long long并离线输出。最好生成树后开两个图，方便处理。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
int max(int x,int y)
{
    return x>y?x:y;
}
struct edge
{
    int from,n,v,nxt,id;
    edge(int from,int n,int v,int nxt)
    {
        this->from=from;
        this->n=n;
        this->v=v;
        this->nxt=nxt;
    }
    edge(int n,int v,int nxt)
    {
        this->n=n;
        this->v=v;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
    friend bool operator <(edge a,edge b)
    {
        return a.v<b.v;
    }
}e[410000],t[410000];
int head[210000],thead[210000],ecnt=-1,tcnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(from,to,v,head[from]);
    e[ecnt].id=ecnt;
    head[from]=ecnt;
    e[++ecnt]=edge(to,from,v,head[to]);
    e[ecnt].id=ecnt;
    head[to]=ecnt;
}
void addt(int from,int to,int v)
{
    t[++tcnt]=edge(to,v,thead[from]);
    thead[from]=tcnt;
    t[++tcnt]=edge(from,v,thead[to]);
    thead[to]=tcnt;
}
int s[210000];
int my_find(int x)
{
    if(s[x]==x)
        return x;
    return s[x]=my_find(s[x]);
}
void my_union(int x,int y)
{
    s[my_find(y)]=my_find(x);
    return;
}
//如果用tarjan，还要树链求RMQ预处理。倍增就可以直接求。
int f[210000][20];
long long fx[210000][20];
int d[210000];
void dfs(int x)
{
    for(int i=thead[x];~i;i=t[i].nxt)
        if(!f[t[i].n][0])
        {
            f[t[i].n][0]=x;
            fx[t[i].n][0]=t[i].v;
            d[t[i].n]=d[x]+1;
            dfs(t[i].n);
        }
}
long long ans[201000];
long long ask(int x,int y)
{
    if(d[x]<d[y])
    {
        int T=x;
        x=y;
        y=T;
    }
    long long ans=0;
    for(int i=18;i>=0;i--)
        if(d[x]-(1<<i)>=d[y])
        {
            ans=max(ans,fx[x][i]);
            x=f[x][i];
        }
    if(x==y)
        return ans;
    for(int i=18;i>=0;i--)
        if(f[x][i]!=f[y][i])
        {
            ans=max(ans,fx[x][i]);
            ans=max(ans,fx[y][i]);
            x=f[x][i];
            y=f[y][i];
        }
    return max(ans,max(fx[x][0],fx[y][0]));
}
int main()
{
    memset(head,-1,sizeof(head));
    memset(thead,-1,sizeof(thead));
    int n,m,u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        s[i]=i;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    std::sort(e,e+ecnt+1);
    long long sum=0,cnt=0;
    for(int i=0;i<=ecnt&&cnt<n-1;i++)
        if(my_find(e[i].from)!=my_find(e[i].n))
        {
            sum+=e[i].v;
            cnt++;
            my_union(e[i].from,e[i].n);
            addt(e[i].from,e[i].n,e[i].v);
        }
    f[1][0]=1;
    fx[1][0]=0;
    d[1]=1;
    dfs(1);
    for(int i=1;i<=18;i++)
        for(int j=1;j<=n;j++)
        {
            f[j][i]=f[f[j][i-1]][i-1];
            fx[j][i]=max(fx[j][i-1],fx[f[j][i-1]][i-1]);
        }
    for(int i=0;i<=ecnt;i++)
        if(!ans[e[i].id>>1])
        {
            if(f[e[i].from][0]==e[i].n||f[e[i].n][0]==e[i].from)
                ans[e[i].id>>1]=sum;
            else
                ans[e[i].id>>1]=sum-ask(e[i].from,e[i].n)+e[i].v;
        }
    for(int i=0;i<m;i++)
        printf("%lld\n",ans[i]);
    return 0;
}