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

作者: wjyyy 分类: LCA,倍增,生成树,解题报告,贪心 发布时间: 2018-07-26 09:12

点击量:23

 

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

 

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;
}

说点什么

avatar
  Subscribe  
提醒
/* */