首页 > ACM题库 > HDU-杭电 > hdu 3942 Everyone Has His Wing Broken待解决[解题报告]C++
2015
04-14

hdu 3942 Everyone Has His Wing Broken待解决[解题报告]C++

Everyone Has His Wing Broken

问题描述 :

Long long ago, N gamblers (numbered from 1 to N) got together to gamble. At that time, the kinds of gamble were not that much diversified. The gamble can only be performed in a way that two people played against each other and the one who lost the game would have to give the winner $1. Furthermore, the one who lose all his money and lose for another time would get out and never come back. But he still has to pay $1 (He may sell his pants). After playing for quite a long time, they felt as if they had their wings broken, for everyone still here won nothing.
As one of the gamblers, mzry1992 wondered what really happened. Now mzry1992 wants you to tell him what happened between some pairs, for example how much does gambler A win from gambler B directly. But actually you do not know the real situation. So you could just tell him one of the possible situations.

输入:

There are T cases and the first line of the input contains the number T. The first line of each case consists of one integer N(2 ≤N≤500), indicating the number of gamblers. Then comes N lines. The i-th line is a non-negative integer smaller than 101 indicating the i-th gambler’s initial possess. The next line contains one integer M(0≤M≤10000), indicating the number of pairs of gamblers who gambled. The following M line contains three integer A, B, t(1≤A, B≤N, 1≤t≤100), which means that the gamble A and the gamble B played the game for t times. The final part of each test case begins with an integer Q (1≤Q≤200000). Then Q lines follows. Each line contains two integers A, B. You are asked to answer how much gambler A wins from B.

输出:

There are T cases and the first line of the input contains the number T. The first line of each case consists of one integer N(2 ≤N≤500), indicating the number of gamblers. Then comes N lines. The i-th line is a non-negative integer smaller than 101 indicating the i-th gambler’s initial possess. The next line contains one integer M(0≤M≤10000), indicating the number of pairs of gamblers who gambled. The following M line contains three integer A, B, t(1≤A, B≤N, 1≤t≤100), which means that the gamble A and the gamble B played the game for t times. The final part of each test case begins with an integer Q (1≤Q≤200000). Then Q lines follows. Each line contains two integers A, B. You are asked to answer how much gambler A wins from B.

样例输入:

3
3
7
5
9
3
1 2 7
1 3 5
2 3 9
1
1 2

3
1
1
20
1
1 2 2
2
1 2
1 3

3
1
1
20
1
1 2 3
2
1 2
1 3

样例输出:

Case 1:
-5
Case 2:
0
0
Case 3:
Impossible!

Hint
The gambles do not have to happen in the given order.


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  3. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts