P4180 【模板】严格次小生成树[BJWC2010]

题目描述

小C最近学了很多最小生成树的算法，Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时，小P又来泼小C冷水了。小P说，让小C求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是EM，严格次小生成树选择的边集是ES，那么需要满足：(value(e)表示边e的权值) $∑e∈EMvalue(e)<∑e∈ESvalue(e)sum_{e in E_M}value(e)<sum_{e in E_S}value(e)∑e∈EMvalue(e)<∑e∈ESvalue(e)$

这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。

输入输出格式

输入格式：

第一行包含两个整数N 和M，表示无向图的点数与边数。接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。

输出格式：

包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

说明

数据中无向图无自环； 50% 的数据N≤2 000 M≤3 000； 80% 的数据N≤50 000 M≤100 000； 100% 的数据N≤100 000 M≤300 000 ，边权值非负且不超过 10^9 。

用非严格最小生成树去边的方法显然时间和正确性都是不对的

思路：跑完最小生成树后穷举在树上添加每一条非树边（x,y)，这条边会与树上x到y的路径形成一个环，这时去掉环上严格次大边即可形成一棵新的生成树

方法：

跑出一棵最小生成树并标记树上的边，（所以我当时到底是怎么想到用prim而不用kruskal的TAT
用倍增预处理出f[i][j]每个点的2^j级祖先和g[i][j][01] 节点i到他的2^j级祖先路径上的最大值和次大值
穷举添加每一条非树边（x,y)，用倍增求lca（x，y）同时找出树上路径中的最大值和次大值
如果最大值与非树边xy相等则比较原答案和最小生成树的边权和减去次大边加上edge[x][y],f否则比较原答案和最小生成树的边权和减去最大边加上edge[x][y]

#include<iostream>
#include<stdio.h>
#include<queue>
#include<cstring>
using namespace std;

int i,m,h,n,j,k,a[700000],f[700000][25],g[700000][25][2],ver[700000]={1},nex[700000],edge[700000],head[700000],cnt;
priority_queue<pair<int,int> > q;
int w[700000],x,y,deep[700000];
bool b[700000],bl[700000];
long long ans=2147483647000000,sum;
void add(int x,int y,int z,int r)
{
    cnt+=1;
    ver[cnt]=y;
    nex[cnt]=head[x]; 
    head[x]=cnt;
    edge[cnt]=z;
    w[cnt]=r;
}

void prim()
{
    memset(a,0x3f,sizeof(a)); a[1]=0;
    q.push(make_pair(0,0));
    for(int l=1;l<=n;l++)
    {
        while(b[ver[q.top().second]]) q.pop();
        int t=q.top().second; q.pop();
        b[ver[t]]=1;	bl[t]=bl[w[t]]=1;
        for(int i=head[ver[t]];i;i=nex[i])
        {
            int e=ver[i];
            if(edge[i]<a[e])
            {
                a[e]=edge[i];
                q.push(make_pair(-a[e],i));
            }
        }
    }
    b[0]=bl[0]=0; ver[0]=0;
}

void dfs(int x,int fa)
{
    for(int i=head[x];i;i=nex[i])
    {
        int t=ver[i];
        if(bl[i]&&(t!=fa)) 
        {
            deep[t]=deep[x]+1;
            g[t][0][0]=edge[i];
            sum+=(long long)edge[i];
            f[t][0]=x;
            dfs(t,x);
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&h,&k);
        add(x,h,k,cnt+2);
        add(h,x,k,cnt);
    }
    for(i=0;i<=n;i++) g[i][0][1]=-0x3f3f3f3f;
    deep[1]=1; prim(); dfs(1,0);
    for(j=1;j<20;j++)
        for(i=1;i<=n;i++) 
            f[i][j]=f[f[i][j-1]][j-1];
    for(j=1;j<20;j++) 
        for(i=1;i<=n;i++)	
        {
            if(!f[i][j]) continue;
            g[i][j][0]=max(g[i][j-1][0],g[f[i][j-1]][j-1][0]);
            if(g[i][j-1][0]==g[f[i][j-1]][j-1][0]) g[i][j][1]=max(g[i][j-1][1],g[f[i][j-1]][j-1][1]);
            if(g[i][j-1][0]<g[f[i][j-1]][j-1][0])  g[i][j][1]=max(g[i][j-1][0],g[f[i][j-1]][j-1][1]);
            if(g[i][j-1][0]>g[f[i][j-1]][j-1][0])  g[i][j][1]=max(g[i][j-1][1],g[f[i][j-1]][j-1][0]);
        }
    for(i=1;i<=cnt;i++)
    {
        if(bl[i]) continue;
        int maxx=-0x3f3f3f3f,mmax=-0x3f3f3f3f;
        x=ver[i]; y=ver[w[i]];
        if(deep[x]<deep[y]) swap(x,y);
        for(j=20;j>=0;j--) 
        if(deep[f[x][j]]>=deep[y]) 
        {
            if(g[x][j][0]>maxx) 
            {
                mmax=maxx,maxx=g[x][j][0];
                if(g[x][j][1]>mmax) mmax=g[x][j][1];
            }
            else if((g[x][j][0]>mmax)&&(maxx!=g[x][j][0])) mmax=g[x][j][0];
            
            x=f[x][j];
        }
        for(j=20;j>=0;j--)
        {
            if(f[x][j]==f[y][j]) continue;
            if(g[x][j][0]>maxx) 
            {
                mmax=maxx,maxx=g[x][j][0];
                if(g[x][j][1]>mmax) mmax=g[x][j][1];
            }
            else if(g[x][j][0]>mmax&&(maxx!=g[x][j][0])) mmax=g[x][j][0];
            
            if(g[y][j][0]>maxx) 
            {
                mmax=maxx,maxx=g[y][j][0];
                if(g[y][j][1]>mmax) mmax=g[y][j][1];
            }
            else if((g[y][j][0]>mmax)&&(maxx!=g[y][j][0])) mmax=g[y][j][0];
            y=f[y][j]; x=f[x][j];
        }
        if(x!=y)
        {
            if(g[x][0][0]>maxx) 
            {
                mmax=maxx,maxx=g[x][0][0];
                if(g[x][0][1]>mmax) mmax=g[x][0][1];
            }
            else if((g[x][0][0]>mmax)&&(maxx!=g[x][0][0])) mmax=g[x][0][0];
            
            if(g[y][0][0]>maxx) 
            {
                mmax=maxx,maxx=g[y][0][0];
                if(g[y][0][1]>mmax) mmax=g[y][0][1];
            }
            else if((g[y][0][0]>mmax)&&(maxx!=g[x][0][0])) mmax=g[y][0][0];
        }
        if(edge[i]==maxx) ans=min(ans,(long long)sum-mmax+maxx);
        else ans=min(ans,(long long)sum-maxx+edge[i]);
        bl[w[i]]=1;
    }
    printf("%lld",ans);
}