题目名称	718. [SDOI 2007] 环球旅行问题
输入输出	`chbtrip.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	sywgz 于2012-04-01加入
开放分组	全部用户
提交状态
分类标签	二分图图论网络流
	分享题解

通过：80，提交：174，通过率：45.98%
SOBER GOOD BOY	100	0.000 s	0.00 MiB	C++
AntiLeaf	100	0.000 s	0.00 MiB	C++
Hzoi_	100	0.000 s	0.00 MiB	C++
面对疾风吧疾风疾风吧	100	0.000 s	0.00 MiB	C++
Troywar	100	0.000 s	0.00 MiB	C++
AAAAAAAAAA	100	0.000 s	0.00 MiB	C++
YGOI_真神名曰驴蛋蛋	100	0.000 s	0.04 MiB	C++
于	100	0.001 s	0.00 MiB	C++
Samle	100	0.002 s	0.00 MiB	C++
Pine	100	0.002 s	0.08 MiB	C++

关于环球旅行问题的近10条评论(全部评论)
哒哒哒哒哒！ 2016-09-13 10:42 6楼
为什么节点编号从0开始就WA，从1开始就A _Itachi 2016-09-02 15:51 5楼
最小路径覆盖 Hzoi_Go灬Fire 2016-08-30 16:20 4楼
千分斩！槿柒 2016-06-16 17:51 3楼
...既然这题被划到网络流的话= = 网络流怎么搞馒头 2013-02-26 14:54 2楼
code Makazeu 2012-04-18 16:27 1楼

718. [SDOI 2007] 环球旅行问题

★★ 输入文件：chbtrip.in 输出文件：chbtrip.out 简单对比
时间限制：1 s 内存限制：128 MiB

【问题描述】
关于哈密顿道路问题大家一定很熟悉吧。该问题和哈密顿问题类似，也是关于环球旅行
的，但是该问题与哈密顿问题不同的是，该题不是 NP 问题。
地球上有 n 个城市，这些城市之间有 m 条单向的道路，这些道路之间不存在回路
（环）。现在CHB 先生想进行多次环球旅行，每次旅行可以在任意城市出发，当然，可以
在任意城市结束。但是，在所有的旅行过程中，不能经过同一城市两次或多于两次。
问题是：
CHB 先生最少需要多少次旅行，才能到达所有的城市？
【输入】(trip.in)
第一行 n m。
以下 m 行，每行两个数 u v，表示 u 到 v 之间有一条路。顶点标号为：0 到n-1
【输出】(trip.out)
最少的旅行次数。
【样例输入】
5 8
4 3
3 2
0 3
4 2
4 0
1 2
0 2
1 0
【样例输出】
2
范围：前 30 ％数据，1 <=n<= 50 m<=200
全部数据 1 <= n <= 500 m <= 5000