保留道路-白红宇

保留道路

阅读量：5850 次

发布时间：2019-06-19

本文共 1360 字，大约阅读时间需要 4 分钟。

这里写图片描述

50%的做法：

先按照s升序排序。

从小到大枚举maxg，把g小于maxg的边全部选出来，（因为前面已经排过序了），造一棵最小生成树，更新答案。时间复杂度≈O(m*m)。

100分的做法：

按照g升序排序。

维护一个n-1条边的边集，是上一个建造的最小生成树的边集。

从前往后枚举maxg，把这条边按照s用插入排序插入到当前n-1条边的集合中。

在这样的n条边的集合中建造一颗最小生成树，最后再把用到的边存到边集中（就是将没用到的删去），从而维护了一个n-1的边集。

刚才所说的边集其实就是维护的一棵最小生成树。

时间复杂度≈O(m*n)。

因为最小生成树的性质：在当前的最小生成树中插入一条边，构成了环，把环中最长的边删去就是新的最小生成树。

60分代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #define LL long long#define N 50009using namespace std;int n,m,f[509];LL Ws,Wg,ans=(1ll*1<<62),order[N];struct H{ int u,v;LL s,g;}b[N];LL maxg,maxs,num;bool cmp(H x,H y) { return x.s

100分做法：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #define LL long long#define N 50009using namespace std;int n,m,f[509],cnt,num;LL ans=(1ll*1<<62);LL Ws,Wg,order[N],r;struct H{ int u,v; LL s,g;}b[N],q[N],tree[N];bool used[N];LL maxg,maxs;bool cmp(H x,H y){ return x.g
           
            ans) continue;//这个剪枝可以减少很多多余的计算 int pos=cnt+1; for(int j=1;j<=cnt;j++) if(tree[j].s>b[i].s) { pos=j;break; } if(pos==cnt+1) tree[++cnt]=b[i]; else { ++cnt; for(int j=cnt;j>pos;j--) tree[j]=tree[j-1]; tree[pos]=b[i]; } if(cnt

转载于:https://www.cnblogs.com/dfsac/p/7587805.html

你可能感兴趣的文章