| 题目名称 | 1761. [国家集训队 2012] 道路染色 |
|---|---|
| 输入输出 | nt2012_coloring.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-10-22加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：6， 提交：11， 通过率：54.55% | ||||
 cstdio |
100 | 0.037 s | 14.56 MiB | C++ |
 小一米 |
100 | 0.984 s | 3.46 MiB | C++ |
 Satoshi |
100 | 1.047 s | 3.38 MiB | C++ |
 梦那边的美好ET |
100 | 1.556 s | 3.67 MiB | C++ |
 shallwe |
100 | 3.323 s | 2.92 MiB | C++ |
|
Satoshi |
100 | 4.523 s | 13.76 MiB | C++ |
|
cstdio |
20 | 0.025 s | 1.21 MiB | C++ |
|
Satoshi |
10 | 18.001 s | 3.38 MiB | C++ |
|
cstdio |
5 | 0.011 s | 1.21 MiB | C++ |
 Troywar |
0 | 0.007 s | 0.45 MiB | C++ |
| 关于 道路染色 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
同样是KM，为什么我的常数那么大......?时间都快赶上费用流了
| ||||
|
这道题到底叫Coloring还是Painting啊……
多次做KM的时候，记得把label初始化为零…… 这题的正解是：由于数据是随机的所以一个看上去过不了的算法实际能过……这才是真·骗分…… 还有，原题的有部分分，原因是“更重要而且更邪恶的是因为标准解法很水很水，所以要为了让一些不太自信的选手以为没有完美解法= =!” 出题人你TM在逗我(╯‵□′)╯︵┻━┻ | ||||
1761. [国家集训队 2012] 道路染色
★★★★ 输入文件：nt2012_coloring.in
输出文件：nt2012_coloring.out
简单对比时间限制：1 s 内存限制：256 MiB
Painting(艾雨青)
时间限制：1.0s 内存限制：256.0MB
【问题描述】
给出一颗n个节点的树，要给每一条边染一个1~n-1的颜色，染颜色i的代价为i，要求同一个节点连出的所有边所染颜色都互不相同，求一个为整棵树染色的方案，使得代价之和尽量小。
【输入格式】
第一行一个正整数n
接下来n-1行，每行两个互不相同的正整数a,b表示节点a与b之间有一条边，保证给出的图是一颗树
接下来n-1行，每行两个互不相同的正整数a,b表示节点a与b之间有一条边，保证给出的图是一颗树
【输出格式】
一行一个正整数，表示你的方案的总代价
【样例输入】
3
1 2
1 3
1 2
1 3
【样例输出】
3
【数据规模和约定】
注意这里的输出格式及评分标准与原题不同，原题有部分分，且要求输出方案。
| Test | N | Test | N |
| 1 | =5 | 11 | =105 |
| 2 | =10 | 12 | =110 |
| 3 | =10 | 13 | =115 |
| 4 | =50 | 14 | =120 |
| 5 | =50 | 15 | =125 |
| 6 | =60 | 16 | =130 |
| 7 | =70 | 17 | =135 |
| 8 | =80 | 18 | =140 |
| 9 | =90 | 19 | =145 |
| 10 | =100 | 20 | =150 |