【BZOJ 2654】tree

Description

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

Input

  第一行V,E,need分别表示点数,边数和需要的白色边数。
  接下来E行
  每行s,t,c,col表示这边的端点(点从0开始标号),边权,颜色(0白色1黑色)。

Output

  一行表示所求生成树的边权和。

Sample Input

2 2 1
0 1 1 1
0 1 2 0

Sample Output

2

HINT

数据规模和约定

  0:V<=10

  1,2,3:V<=15

  0,..,19:V<=50000,E<=100000

  所有数据边权为[1,100]中的正整数。

orz 王梦迪大神

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int N=50010;
 5 struct ee{int x,y,w,c;}e[N*2];
 6 int fa[N];
 7 int ans,E,V,need,tot;
 8 int root(int x){
 9     if(fa[x]==x) return x;
10     fa[x]=root(fa[x]);return fa[x];
11 }
12
13 bool cmp(ee a,ee b){
14     if(a.w==b.w) return a.c<b.c;
15     return a.w<b.w;
16 }
17
18 int kls(){
19     tot=0;int sum=0,num=0;
20     for(int i=0;i<V;i++) fa[i]=i;
21     for(int i=1;i<=E&&sum<V-1;i++){
22         int xx=root(e[i].x),yy=root(e[i].y);
23         if(xx!=yy) fa[xx]=yy,sum++,tot+=e[i].w,num+=(e[i].c==0);
24     }
25     return num;
26 }
27 int main(){
28     scanf("%d%d%d",&V,&E,&need);
29     int s,t,w,c;
30     for (int i=1;i<=E;i++){
31         scanf("%d%d%d%d",&s,&t,&w,&c);
32         e[i].x=s;e[i].y=t;e[i].w=w;e[i].c=c;
33     }
34     int l=-100,r=100;
35     while(l<=r){
36         int mid=(l+r)>>1;
37         for (int i=1;i<=E;i++) if(e[i].c==0)e[i].w+=mid;
38         sort(e+1,e+1+E,cmp);
39         int h=kls();
40         if(h>=need) ans=(tot-need*mid),l=mid+1;else r=mid-1;
41     //ans这里要注意一下,1wa
42         for (int i=1;i<=E;i++) if(e[i].c==0)e[i].w-=mid;
43     }
44     printf("%d",ans);
45 }
时间: 02-14

【BZOJ 2654】tree的相关文章

【BZOJ 2654】 MST

2654: tree Description 给你一个无向带权连通图,每条边是黑色或白色.让你求一棵最小权的恰好有need条白色边的生成树. 题目保证有解. Input 第一行V,E,need分别表示点数,边数和需要的白色边数. 接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号),边权,颜色(0白色1黑色). Output 一行表示所求生成树的边权和. V<=50000,E<=100000,所有数据边权为[1,100]中的正整数. Sample Input 2 2 1 0 1

【BZOJ 3282】Tree Link Cut Tree模板题

知道了为什么要换根(changeroot),access后为什么有时要splay,以及LCT的其他操作,算是比较全面的啦吧,,, 现在才知道这些,,,真心弱,,, #include<cstdio> #include<algorithm> #define read(x) x=getint() using namespace std; const int N=300003; inline int getint(){char c;int ret=0;for(c=getchar();c&l

【BZOJ 1468】Tree 点分治

点分治$O(nlogn)$ 坚持到月考结束后新校就剩下我一个OIer,其他人早已停课了,老师估计懒得为我一个人开机房门,让我跟班主任说了一声,今晚就回到了老校,开始了自己都没有想到会来的这么早的停课生活. 所以先水一道点分治 #include<cstdio> #include<algorithm> #define read(x) x=getint() #define N 40003 #define max(a,b) (a)>(b)?(a):(b) using namespac

【BZOJ 2820】 YY的GCD

2820: YY的GCD Time Limit: 10 Sec  Memory Limit: 512 MB Submit: 807  Solved: 404 [Submit][Status] Description 神犇YY虐完数论后给傻×kAc出了一题 给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对 kAc这种傻×必然不会了,于是向你来请教-- 多组输入 Input 第一行一个整数T 表述数据组数 接下来T行,每行两个正整数,表示

【BZOJ 1854】 [Scoi2010]游戏

1854: [Scoi2010]游戏 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 2609  Solved: 931 [Submit][Status] Description lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示.当他使用某种装备时,他只能使用该装备的某一个属性.并且每种装备最多只能使用一次. 游戏进行到最后,lxhgww遇到了终极boss,这个终极bos

【BZOJ 1036】【ZJOI 2008】树的统计

此题为树链剖分的裸题. 代码如下,使用常用的轻重链剖分. /************************************************************** Problem: 1036 User: Evensgn Language: C++ Result: Accepted Time:2468 ms Memory:5772 kb ****************************************************************/ #inc

【BZOJ 1150】 1150: [CTSC2007]数据备份Backup (贪心+优先队列)

1150: [CTSC2007]数据备份Backup Description 你在一家 IT 公司为大型写字楼或办公楼(offices)的计算机数据做备份.然而数据备份的工作是枯燥乏味 的,因此你想设计一个系统让不同的办公楼彼此之间互相备份,而你则坐在家中尽享计算机游戏的乐趣.已知办公 楼都位于同一条街上.你决定给这些办公楼配对(两个一组).每一对办公楼可以通过在这两个建筑物之间铺设网 络电缆使得它们可以互相备份.然而,网络电缆的费用很高.当地电信公司仅能为你提供 K 条网络电缆,这意味 着你仅

【BZOJ 2823】 [AHOI2012]信号塔

2823: [AHOI2012]信号塔 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 469  Solved: 198 [Submit][Status][Discuss] Description 在野外训练中,为了确保每位参加集训的成员安全,实时的掌握和收集周边环境和队员信息非常重要,集训队采用的方式是在训练所在地散布N个小型传感器来收集并传递信息,这些传感器只与设在集训地中的信号塔进行通信,信号塔接收信号的覆盖范围是圆形,可以接收到所有分布在

【BZOJ 3190】 [JLOI2013]赛车

3190: [JLOI2013]赛车 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 803 Solved: 279 [Submit][Status][Discuss] Description 这里有一辆赛车比赛正在进行,赛场上一共有N辆车,分别称为个g1,g2--gn.赛道是一条无限长的直线.最初,gi位于距离起跑线前进ki的位置.比赛开始后,车辆gi将会以vi单位每秒的恒定速度行驶.在这个比赛过程中,如果一辆赛车曾经处于领跑位置的话(即没有其他