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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 300010using namespace std;int n,m,x,y,z,k,sum,tot,num,answer=N,fa[N],ans[N];int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}struct Edge{    int x,y,z;}edge[N];int cmp(Edge a,Edge b){    return a.z

转载于:https://www.cnblogs.com/z360/p/7391022.html

你可能感兴趣的文章