首页 > 其他分享 >loj #10069. 「一本通 3.1 练习 4」Tree

loj #10069. 「一本通 3.1 练习 4」Tree

时间:2022-11-11 17:47:19浏览次数:55  
标签:loj 10069 Tree long int 3.1

给你一个无向带权连通图,每条边是黑色或白色。求一棵最小权的恰好有 K 条白色边的生成树。题目保证有解

 

 二分一个增加量md,  给每个白边权值加md , 跑一下kruskal , 看贪心取了多少白边,和K比较检验答案

 

#include <bits/stdc++.h>
using namespace std ; 
 const int N=2e5;
 #define int long long 
 int n,m,K,tot;
 int S;
 int f[N];
 struct E{ int x,y,z,col; }a[N];
 
 int cmp(E x,E y){ 
   if(x.z==y.z) return x.col<y.col; 
   return x.z<y.z; 
 }
 
 int find(int x){
     return x==f[x]?x:f[x]=find(f[x]);
 }
 void add(int x,int y,int z,int col){
     tot++; a[tot].x=x,a[tot].y=y,a[tot].z=z; 
     a[tot].col=col;
 }
 int chk(int md){
     S=0;
     int i,fx,fy,ans=0,cnt=0;
     
     for(i=0;i<n;i++) f[i]=i;
     for(i=1;i<=tot;i++) if(a[i].col==0) a[i].z+=md;
     sort(a+1,a+1+tot,cmp);
     
     for(i=1;i<=tot;i++){
           fx=find(a[i].x),fy=find(a[i].y);
           
           if(fx!=fy){
               S+=a[i].z;
             if(a[i].col==0) ans++;
              f[fx]=fy; 
              cnt++;
         }
           if(cnt==n-1) break;
    }
    for(i=1;i<=tot;i++) if(a[i].col==0) a[i].z-=md;
    return ans>=K;
 }
 
 main(){
     int i,x,y,z,t;
     cin>>n>>m>>K;
     for(i=1;i<=m;i++) cin>>x>>y>>z>>t,add(x,y,z,t);
     
     int ans=0;
     int l=-1e4,r=1e4;
     while(l<=r){
         int md=(l+r)/2;
         if(chk(md)) l=md+1,ans=S-K*md; else r=md-1;
     }
     cout<<ans;
 }
 
 
 
 

 

标签:loj,10069,Tree,long,int,3.1
From: https://www.cnblogs.com/towboa/p/16881255.html

相关文章

  • CodeForces - 1156D 0-1-Tree
    题意:给出一棵树,树的边权只有0和1。求有多少有序点对,其最短路径上每条权值为0的边不紧跟在权值为1的边后面。解:合法路径如下所示:000000 111111 000111 随便找个结点为......
  • loj#10064 黑暗城堡
     求图中的最短路径生成树有多少个?(该生成树中的任意点i,i到1的距离和 原图中的i到1的最短距离相等  跑所有点到1的单源最短路,d[i] ifd[i]==d[y]+z,那么z这个路......
  • 动态构建TreeView(中国省市区)
    .aspx代码如下:<%@PageLanguage="C#"AutoEventWireup="true"CodeFile="中国市区县.aspx.cs"Inherits="中国市区县"%><!DOCTYPEhtmlPUBLIC"-//W3C//DTDXHTML1.0......
  • E. Paimon Segment Tree
    传送门题意:首先给出n,m,q,一个长度为n的数组,m次修改操作,每次修改操作,l,r,x,对l,r区间里面的数加上k,q次询问操作,每次询问操作,问\(\sum\limits_{i=lk}^{rk}\s......
  • 涨姿势 之 Sourcetree 显示头像
    LZ-Says:莫名情愫,嗷呜前言生命不止,折腾不止,哇咔咔。目前Git较为好用的莫过于Sourcetree,简单方便快速,666,而今天在看Git提交记录时,突然感觉头像丑的一批,一起瞅瞅:左上......
  • 「LOJ2474」北校门的未来
    题目点这里看题目。你有一棵树\(T\),初始时\(T=(V=\{1\},E=\varnothing)\)。你将要进行\(q\)次操作,每次操作的形式为以下两种之一:第一种操作:给定参数\(x,y\),保证......
  • 软件篇 之 Mac Sourcetree 安装使用
    LZ-Says:今天安装网,怎一个曲折。不过从而也明白了信任,感谢。前言新系统,安装、配置好多东西,有点乱。这里简单记录下过程,避免后续脑子2333白白浪费时间。点滴积累,加油开撸......
  • vue el-tree树形结构选中子节点,保持父节点选中
    <!--菜单分配弹窗--><el-dialogtitle="菜单分配":visible.sync="menuDialogVisible"width="30%"><el-tree:props="props"......
  • C. DFS Trees
    C.DFSTreeshttps://codeforces.ml/contest/1707/problem/C题意\(findMST(i)\)代表从点i开始,按照一下算法,生成的生成树(不一定是最小生成树)。问i取1~n,findMST(i)是......
  • HDU 5379 Mahjong tree
    ProblemDescriptionLittlesunisanartist.Todayheisplayingmahjongalone.Hesuddenlyfeelsthatthetreeintheyarddoesn'tlookgood.Sohewant......