设为首页 加入收藏

TOP

HDU 4786 Fibonacci Tree 最小生成树变形
2015-07-20 17:58:47 来源: 作者: 【 】 浏览:3
Tags:HDU 4786 Fibonacci Tree 最小 生成 变形

思路:

这题比赛的时候想了好久,最后队友机智的想到了。

不过那时不是我敲的,现在敲的1A。

想好就容易了。

直接把1或者0当做边的权值,然后按边从小到大排序,然后算最小生成用到了几条白边,然后再按边从大到小排序,然后再算白边用了几条。然后最小和最大需要用到的白边都算出来了。如果在这最小最大区间中存在那个啥数列的话就是Yes,否则就是No。

为什么在这区间里面就是对的呢?刚开始我也想了好久,然后发现,因为白边权值是1,然后黑边是0,然后假设用到白边最小的是6,最大的是10,那么,我们可以用黑边去替代两条白边,生成树就是有8条白边了,而正好是我们要找的数列中的数。其实还是有点抽象……自己脑子想想吧……

#include
  
   
#include
   
     #include
    
      #include
     
       #include
       #include
       
         #include
        
          #include
         
           #include
          
            #define mem(a,b) memset(a,b,sizeof(a)) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define INF 510010 #define maxn 1000010 using namespace std; typedef long long ll; typedef unsigned long long ull; int f[maxn],fib[92]; struct abc { int u,v,w; }a[maxn]; bool cmp1(abc a,abc b) { return a.w
           
            b.w; } void Fib() { fib[1]=1;fib[2]=2; for(int i=3;i<41;i++) fib[i]=fib[i-1]+fib[i-2]; } int find(int x) { return x==f[x]?x:f[x]=find(f[x]); } void init() { for(int i=0;i
            
             >t; Fib(); for(int kk=1;kk<=t;kk++) { int n,m,i; scanf("%d%d",&n,&m); for(i=0;i
             
              

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇杭电 1846(巴什博弈) 下一篇uva 11927 - Games Are Important..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: