[SDOI2007]环球旅行问题

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 chbtrip.in 输出文件 chbtrip.out
【问题描述】
关于哈密顿道路问题大家一定很熟悉吧。该问题和哈密顿问题类似,也是关于环球旅行
的,但是该问题与哈密顿问题不同的是,该题不是 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