| 题目名称 | 426. 血帆海盗 |
|---|---|
| 输入输出 | bloodsail.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 .Xmz
于2010-04-13加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：81， 提交：214， 通过率：37.85% | ||||
 Anonymity |
100 | 0.322 s | 2.91 MiB | C++ |
 jhs |
100 | 0.328 s | 5.12 MiB | C++ |
 Hzoi_Maple |
100 | 0.332 s | 9.36 MiB | C++ |
 Hzoi_QTY |
100 | 0.335 s | 4.74 MiB | C++ |
 甘罗 |
100 | 0.337 s | 12.90 MiB | C++ |
 Marvolo |
100 | 0.340 s | 12.90 MiB | C++ |
 Hzoi_Mafia |
100 | 0.345 s | 3.64 MiB | C++ |
|
Anonymity |
100 | 0.362 s | 7.27 MiB | C++ |
|
Hzoi_Maple |
100 | 0.371 s | 18.72 MiB | C++ |
 test |
100 | 0.374 s | 10.23 MiB | C++ |
| 关于 血帆海盗 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
编译器炸了
在没有编译运行的情况下交了3遍 发现没过编译，没过样例= = Hzoi_Mafia
2017-07-31 19:34
7楼
| ||||
 HZOI_蒟蒻一只
2017-07-31 09:35
6楼
| ||||
|
| ||||
|
| ||||
|
和HAOI2017T1撞车……然而没有切掉，真是可惜。
 FoolMike
2017-04-25 20:44
3楼
| ||||
|
终于过了
 | ||||
|
Orz BYVoid
| ||||
Hzoi_moyi
天一阁
ztx【问题描述】
随着资本的扩大，藏宝海湾贸易亲王在卡利姆多和东部王国大陆各建立了N/2 个港口。大灾变发生以后，这些港口之间失去了联系，相继脱离了藏宝海湾贸易亲王的管辖，各自为政。利益的驱动使得每个港口都想和对岸大陆的另一个港口建立贸易合作关系，由于地理位置因素，只有存在直接到达的航线的两个港口才能建立合作，而且每个港口只与对岸一个港口建立合作，因此并不是所有的港口都能找到合作伙伴。
血帆海盗得知这一消息以后，决定对其中一条航线进行干扰性的掠夺。经过分析，血帆海盗计算出最多能有W 对港口合作。如果两个港口之间只有一条航线，而且这条航线恰好是血帆海盗要掠夺的航线，这两个港口将不能建立合作关系。血帆海盗指挥官菲尔拉伦想知道他们有几种选择，可以让地精们无法建立W 对港口。
【输入格式】
第1行，两个整数N,M，表示一共的港口个数和航线条数。
接下来M行，每行两个整数A,B，表示卡利姆多的港口A与东部王国的港口B之间有一条航线直接连接，其中1<=A<=N/2，N/2+1<=B<=N。
【输出格式】
一个整数，表示血帆海盗可以选择掠夺的航线条数。
解释：如果掠夺一条航线以后，地精依然可以建立起最多的W个合作关系（可以有多种），
那么这条航线是不值得掠夺的，否则就是掠夺方案之一。
【样例输入】
8 5 1 5 1 6 2 7 3 7 4 8
【样例输出】
1
【样例说明】
地精做多能建立起合作关系的数量为3，掠夺(4,8)这条航线后，最多能建立的合作关系的数量减少为2。
【数据规模】
40%的数据满足2<=N<=200，1<=M<=1000
100%的数据满足2<=N<=100000，1<=M<=100000，保证N为偶数
【题目来源】
by BYVoid