首页 > ACM题库 > HDU-杭电 > hdu 2249 最小费用狗待解决[解题报告]C++
2014
01-04

hdu 2249 最小费用狗待解决[解题报告]C++

最小费用狗

问题描述 :

在地球上的一个鲜为人知的角落,住着这样一群人.他们整日与算法为伴,以研究出高效的算法为荣.就连竞选村长都是以Word Final的标准进行的.这里的算法风气之浓厚,就连当地的动物们都受到了极大的影响.旺财是村长–TCL(相当于世界冠军的水平)的爱犬,从小就受到村长一家的熏陶,当别的小动物都还在算A+B的的时候,旺财已经学会"迪杰斯特拉"和"贝尔曼-佛德"了,因此他一直是当地的小动物们崇拜的对象,它们眼中的最有希望进Animal Kingdom World Final的明日之星,就连村里面耕地的老牛们见了他都要叫声"大牛好~".
可是,旺财也有他的苦衷.TCL对待他实在是太好了,每天都请医疗专家周海角为旺财开出许多的保健药品(据说TCL那么牛就是因为从小吃周海角开的药).周海角作为一名医疗专家,有着数十年的江湖行医经验,他的药方不是一般人能开得出来的.他每次都会开出两张药方,第一张药方上写有N1种药品(每种药的编号分别为1,2,3……,N1),第二张药方上写有N2种药品(编号分别为N1+1,N1+2,N1+3……,N1+N2),之所以要这样,是因为第一张药方上的药只有村北的药店里才有,而第二张药方上的药只有村南的药店里才有,并且,药方上还明确指出哪些药必须在哪些药服用之后才能服用,否则会有脑残的危险!还需要一提的药是不能打包带回去,只能在相应的药店里在专家指导下当场服用,安全第一嘛。旺财还面临的一个问题是:村北和村南的药店相隔甚远,而且两地之间还有一个规定凡是4条腿或4个轮子的东西经过都要交钱的收费站,作为一条精通算法的小狗,旺财始终把"提高效率减小耗费"作为自己的座右铭.他在想要怎样吃药才能使跑远路的次数最少,这样过路费也会最小.从村南到村北或从村北到村南算一次跑远路,到最后吃完药跑回家,也算一次哦.

输入:

有多组输入数据.每组数组的第一行有三个整数N1, N2, M. 接下来有M行数组,每行有两个整数 a, b, 分别表示在吃第a种药之前,需要先吃第b种药. 最后一组数据后,会有三个0表示输入结束。所有的数据中, 1<=N1,N2<=60000, 0<=M<=120000, 1<=a,b<=N1+N2.

输出:

有多组输入数据.每组数组的第一行有三个整数N1, N2, M. 接下来有M行数组,每行有两个整数 a, b, 分别表示在吃第a种药之前,需要先吃第b种药. 最后一组数据后,会有三个0表示输入结束。所有的数据中, 1<=N1,N2<=60000, 0<=M<=120000, 1<=a,b<=N1+N2.

样例输入:

5 3 3
1 2
5 1
3 2
0 0 0

样例输出:

3


  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  2. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法