BZOJ 1977 严格次小生成树

小C最近学了很多最小生成树的算法，Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时，小P又来泼小C冷水了。小P说，让小C求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是EM，严格次小生成树选择的边集是ES，那么需要满足：(value(e)表示边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：

11

题解：严格次小生成树和非严格次小生成树的思想其实差不多，无非是多维护一个u->v之间的次大值
然后这显然也是能用倍增维护的
如果把最大边拆去换成新边后整棵树仍是最小生成树，那么就换次大边用，再不对就不用
这样能保证求出的一定不是最小生成树，所以是严格次小的
代码如下：

#pragma GCC optimize(3)

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define mp make_pair

#define int long long

#define pii pair<long long,long long>

using namespace std;

struct node

{

    int from,to,cost;

} e[];

int n,m,f[],ans,ans1,vis[],fa[][],d1[][],d2[][],deep[];

vector<pii> g[];

int cmp(node a,node b)

{

    return a.cost<b.cost;

}

void dfs(int now,int ff,int dep,int dis)

{

    deep[now]=dep;

    d1[][now]=dis;

    fa[][now]=ff;

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

    {

        fa[i][now]=fa[i-][fa[i-][now]];

    }

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

    {

        register int a[];

        a[]=d1[i-][now];

        a[]=d1[i-][fa[i-][now]];

        a[]=d2[i-][now];

        a[]=d2[i-][fa[i-][now]];

        sort(a,a+);

        d1[i][now]=a[];

        d2[i][now]=a[];

    }

    for(int i=; i<g[now].size(); i++)

    {

        if(g[now][i].first==ff) continue;

        dfs(g[now][i].first,now,dep+,g[now][i].second);

    }

}

pii get1(int u,int v)

{

    int di=0ll,di2=0ll;

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

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

    {

        if(deep[fa[i][u]]>=deep[v])

        {

            register int a[];

            a[]=di;

            a[]=di2;

            a[]=d1[i][u];

            a[]=d2[i][u];

            sort(a,a+);

            di=a[];

            di2=a[];

            u=fa[i][u];

        }

    }

    if(u==v) return mp(di,di2);

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

    {

        if(fa[i][u]!=fa[i][v])

        {

            register int a[];

            a[]=di;

            a[]=di2;

            a[]=d1[i][u];

            a[]=d1[i][v];

            a[]=d2[i][u];

            a[]=d2[i][v];

            sort(a,a+);

            di=a[];

            di2=a[];

            u=fa[i][u];

            v=fa[i][v];

        }

    }

    register int a[];

    a[]=di;

    a[]=di2;

    a[]=d1[][u];

    a[]=d1[][v];

    a[]=d2[][u];

    a[]=d2[][v];

    sort(a,a+);

    di=a[];

    di2=a[];

    return mp(di,di2);

}

void init()

{

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

    {

        f[i]=i;

    }

}

int find(int x)

{

    if(f[x]==x) return x;

    return f[x]=find(f[x]);

}

void unity(int i,int x,int y,int cost)

{

    int fx=find(x);

    int fy=find(y);

    if(fx==fy) return ;

    ans+=cost;

    f[fy]=fx;

    g[x].push_back(mp(y,cost));

    g[y].push_back(mp(x,cost));

    vis[i]=;

}

signed main()

{

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

    init();

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

    {

        scanf("%lld%lld%lld",&e[i].from,&e[i].to,&e[i].cost);

    }

    sort(e+,e+m+,cmp);

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

    {

        unity(i,e[i].from,e[i].to,e[i].cost);

    }

    dfs(,,,);

    ans1=1e16;

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

    {

        if(!vis[i])

        {

            pii tmp=get1(e[i].from,e[i].to);

            int ans2=ans-tmp.first+e[i].cost;

            int ans3=ans-tmp.second+e[i].cost;

            if(ans==ans2)

            {

                if(ans<ans3) ans1=min(ans1,ans3);

            }

            else

            {

                ans1=min(ans1,ans2);

            }

        }

    }

    printf("%lld\n",ans1);

}