[bzoj2654] tree-白红宇的个人博客

[bzoj2654] tree

发布日期：2021-08-13 01:52:06 浏览次数：2 分类：技术文章

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

　　一开始以为先取need条最短的白边就行了。。然而那样子的话可能图根本没法联通= =

　　网上题解讲的挺清晰的。。就是二分把全部白边加上mid，然后看mst里面有多少条白边。有need条白边的时候再把加上的值减去，就是答案了。

　　但可能出现取不了need条白边的情况（二分mid取到>need条，二分mid+1时取到<need条）

　　这时候就是因为图中有一些黑边和白边权值相同。。那显然我们取的是黑边还是白边是可以替换的。。

　　所以取到>=need条白边的时候就可以更新答案。注意权值相同的话优先先取白边

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int maxn=100233; 7 struct zs{ 8     int u,v,dis; 9 }e[maxn],e1[maxn];int t,t1;10 int fa[maxn],id[maxn];11 int i,j,k,n,m,ans,a,b,c,d,now,l,r,mid;12 13 int ra;char rx;14 inline int read(){15     rx=getchar(),ra=0;16     while(rx<'0'||rx>'9')rx=getchar();17     while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra;18 }19 bool cmp(int a,int b){
    return e[a].dis==e[b].dis?a
          
           
            =k)ans=now-mid*k,l=mid+1;50 else r=mid-1;51 }52 printf("%d\n",ans);53 return 0;54 }

View Code

转载于:https://www.cnblogs.com/czllgzmzl/p/5301618.html

转载地址：https://blog.csdn.net/weixin_30672295/article/details/96195689 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：C++类总结

下一篇：jdk安装和环境变量配置

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章