首页 > ACM题库 > HDU-杭电 > hdu 3494 Dangerous Situation待解决[解题报告]C++
2014
04-04

hdu 3494 Dangerous Situation待解决[解题报告]C++

Dangerous Situation

问题描述 :

Long long time ago, there was one island with several village. People living on the island choose one leader as the CHIEF per four years. This time, a leader was picked to continue in office for another term but not all the people support him, especially the owner of the supermarkets and supplier in villages because he has promised to build roads between each village but no roads seemed to be under constructed.
To get the support of the owners, the chief was thinking about building roads. But the situation was more dangerous because the chief was so mean that he decide to build roads only with the most reasonable price and he want to build as less roads as possible even if no roads can be built between two villages . Engineer Ei come up with different plan of road construction with different price Pi and capability Ci. Only the the road with the highest Ci/Pi rate will be picked as the final plan.
On the exciting day, the chief will gather all the plan the engineers come up with and decide whether each of them is packed or not. The chief will check the list on which the plans are listed with the order based on the time when the plan was submitted to the chief. A road building plan was changed only if there is a better Ci/Pi connecting the same points.
However, not all the one will satisfy. If the one of the supermarkets can’t get enough goods from the supplier, or the suppliers cannot sell his goods to any of the supermarket, the rich owners will gather their wealth and impeach the chief, and the chief will surely step down the office as his enemy was so powerful. Your job is to find out whether the chief can survive this dangerous situation.

输入:

The input will have several test cases. First line is t (t<=10) integer t indicating the number of test cases. Then comes two integers n (n<=200) and m which indicate the number of villages and the number of supermarket (the number of supplier is n-m). Next m line is 2 number in line i where Si and Di (Di<=1000) indicate the supermarket located in the ith village have a demand of Di (the else ones are suppliers). The next line has a number p (p<=5000) indicating the number of road plans. Then p lines followed with four integers per line, s, e, c (c<=1000), v (v<=1000) indicating the start, the end, the capability, the price of the road engineer come up with.

输出:

The input will have several test cases. First line is t (t<=10) integer t indicating the number of test cases. Then comes two integers n (n<=200) and m which indicate the number of villages and the number of supermarket (the number of supplier is n-m). Next m line is 2 number in line i where Si and Di (Di<=1000) indicate the supermarket located in the ith village have a demand of Di (the else ones are suppliers). The next line has a number p (p<=5000) indicating the number of road plans. Then p lines followed with four integers per line, s, e, c (c<=1000), v (v<=1000) indicating the start, the end, the capability, the price of the road engineer come up with.

样例输入:

1
4 2
1 100
2 100
3
1 2 200 40
1 3 200 40
2 4 200 30

样例输出:

Yes


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

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