| 题目名称 | 1764. [国家集训队 2012] tree(陈立杰) |
|---|---|
| 输入输出 | nt2012_tree.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 1024 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-10-22加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：92， 提交：338， 通过率：27.22% | ||||
 梦那边的美好ET |
100 | 0.789 s | 8.56 MiB | C++ |
 LGLJ |
100 | 0.803 s | 9.30 MiB | C++ |
 changxv |
100 | 0.882 s | 2.03 MiB | C++ |
 ztx |
100 | 0.886 s | 2.77 MiB | C++ |
 BaDBoY |
100 | 0.916 s | 1.12 MiB | C++ |
 炎帝 |
100 | 0.935 s | 2.03 MiB | C++ |
 cstdio |
100 | 0.959 s | 2.03 MiB | C++ |
 Samle |
100 | 0.982 s | 1.68 MiB | C++ |
 Hzoi_QTY |
100 | 0.986 s | 1.43 MiB | C++ |
 Hzoi_Mafia |
100 | 1.008 s | 3.50 MiB | C++ |
| 关于 tree(陈立杰) 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
orzWJMZBMR！！！！！
 HZOI_蒟蒻一只
2017-08-14 10:33
9楼
| ||||
|
二分白点的△（derta）
V，之后k l s k e | ||||
|
这题不想说啥了
| ||||
|
二分出来一定要判断白边个数是否大于num，否则加1
| ||||
|
为什么排序时以颜色为第二关键字就对了？
 AAAAAAAAAA
2017-07-20 15:52
5楼
| ||||
|
回复 @cstdio :
垂死梦中惊坐起，膜拜神犇王(chen)梦(li)迪(jie)。 | ||||
|
这题好简单啊
 vampire
2015-09-27 20:14
3楼
| ||||
|
Orz梦迪大神0.959s+秒过
| ||||
|
这题神思路……
可以发现如果分别给白边加-101~101，形成的“合法白边数”区间加起来一定不会漏，因为给白边加x的最少白边数，和给白边加x+1的最多白边数其实是一个意思（二者在Kruskal时加边顺序相同） | ||||
하루Kiev 
天亮说晚安·
FoolMike
天一阁1764. [国家集训队 2012] tree(陈立杰)
★★★ 输入文件：nt2012_tree.in
输出文件：nt2012_tree.out
简单对比时间限制：3 s 内存限制：1024 MiB
【题目描述】
给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。
题目保证有解。
【输入格式】
第一行V,E,need分别表示点数，边数和需要的白色边数。
接下来E行
每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。
【输出格式】
一行表示所求生成树的边权和。
【数据规模和约定】
0:V<=10
1,2,3:V<=15
0,..,19:V<=50000,E<=100000
所有数据边权为[1,100]中的正整数。
【样例输入】
2 2 1 0 1 1 1 0 1 2 0
【样例输出】
2
【题目来源】
tree(陈立杰)