最小费用 ?

Problem Description
在地球上的一个鲜为人知的角落,住着这样一群人.他们整日与算法为伴,以研究出高效的算法为荣.就连竞选村长都是以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个轮子的东西经过都要交钱的收费站,作为一条精通算法的小狗,旺财始终把"提高效率减小耗费"作为自己的座右铭.他在想要怎样吃药才能使跑远路的次数最少,这样过路费也会最小.从村南到村北或从村北到村南算一次跑远路,到最后吃完药跑回家,也算一次哦.

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

Output
每组数据输出一个整数,表示旺财把药房上的药吃完所需的跑远路的次数.

Sample Input
5 3 3
1 2
5 1
3 2
0 0 0

Sample Output
3

qq_40946921
Italink 120000种保健品,堆起来都能把旺财给活埋了,这怎么吃
大约一年之前 回复

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!