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。。。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 300010
using namespace std;
int n,m,x,y,z,k,sum,tot,num,answer=N,fa[N],ans[N];
int read()
{
    ,f=; char ch=getchar();
    ; ch=getchar();}
    +ch-'; ch=getchar();}
    return x*f;
}
struct Edge
{
    int x,y,z;
}edge[N];
int cmp(Edge a,Edge b)
{
    return a.z<b.z;
}
int find(int x)
{
    if(x==fa[x]) return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
int main()
{
    freopen("mst2.in","r",stdin);
    freopen("mst2.out","w",stdout);
    n=read(),m=read();
    ;i<=m;i++)
    {
        x=read(),y=read(),z=read();
        edge[i].x=x;
        edge[i].y=y;
        edge[i].z=z;
    }
    ;i<=n;i++) fa[i]=i;
    sort(edge+,edge++m,cmp);
    ;i<=m;i++)
    {
        int fx=find(edge[i].x),fy=find(edge[i].y);
        if(fx==fy) continue;
        tot++;fa[fx]=fy;
        ans[tot]=i;sum+=edge[i].z;
        ) break;
    }
    ;i<=tot;i++)
    {
        k=,num=;
        ;j<=n;j++) fa[j]=j;
        sort(edge+,edge++m,cmp);
        ;j<=m;j++)
        {
            if(j==ans[i]) continue;
            int fx=find(edge[j].x),fy=find(edge[j].y);
            if(fx!=fy)
            {
                fa[fx]=fy;
                num++;
                k+=edge[j].z;
            }
            ) break;
        }
        &&k!=sum) answer=min(k,answer);
    }
    printf("%d",answer);
}

巴特西

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