COGS 1578. 次小生成树初级练习题

☆ 输入文件：mst2.in 输出文件：mst2.out 简单对比
时间限制：1 s 内存限制：256 MB

【题目描述】

求严格次小生成树

【输入格式】

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

【输出格式】

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

【样例输入】

5 6

1 2 1

1 3 2

2 4 3

3 5 4

3 4 3

4 5 6

【样例输出】

【提示】

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

【来源】

bzoj。。。

求次小生成树的两种方法

1：首先求出最小生成树T，然后枚举最小生成树上的边，计算除了枚举的当前最小
生成树的边以外的所有边形成的最小生成树Ti，然后求最小的Ti就是次小生成树。
2：首先计算出最小生成树T，然后对最小生成树上任意不相邻的两个点（i,j）
添加最小生成树以外的存在的边形成环，然后寻找i与j之间最小生成树上最长的边删去，
计算map[i][j]（最小生成树以外存在的边）与 maxd[i][j]（最小生成树上最长的边）
差值，求出最小的来，w(T)再加上最小的差值就是次小生成树了。

此代码采用的是第一种

屠龙宝刀点击就送

#include <algorithm>

#include <cstdio>

#define M 300500

#define N 100500

using namespace std;

struct Edge

{

    int x,y,z;

    bool operator<(Edge a)const

    {

        return z<a.z;

    }

}edge[M];

int nt[N],fa[N],n,m,zx,ans=0x7fffffff;

int find_(int x) {return x==fa[x]?x:fa[x]=find_(fa[x]);}

int main()

{

    freopen("mst2.in","r",stdin);

    freopen("mst2.out","w",stdout);

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

    for(int x,y,z,i=;i<=m;i++)

    {

        scanf("%d%d%d",&x,&y,&z);

        edge[i]=(Edge){x,y,z};

    }

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

    sort(edge+,edge++m);

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

    {

        int fx=find_(edge[i].x),fy=find_(edge[i].y);

        if(fx!=fy)

        {

            fa[fy]=fx;

            num++;

            nt[num]=i;

            zx+=edge[i].z;

            if(num==n-) break;

        }

    }

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

    {

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

        int num_=,now=;

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

        {

            if(j==nt[i]) continue;

            int fx=find_(edge[j].x),fy=find_(edge[j].y);

            if(fx!=fy)

            {

                fa[fy]=fx;

                now+=edge[j].z;

                num_++;

                if(num_==n-) break;

            }

        }

        if(num_==n-&&now!=zx) ans=min(ans,now);

    }

    printf("%d\n",ans);

    return ;

}