ZOJ Problem Set - 3352
You know, when Lanrete and DD are together, they are always playing boring board games. And they invent the games themselves! Here is yet another boring board games between Lanrete and DD.
They play this game on a directed acyclic graph with N vertices numbered from 0 to N-1 (1 <= N <= 50). For each vertex, their is a digit on it, the digit will be 0, 1, or 2. There are also two flags, a white one and a black one, on the vertices of the graph, initially in vertex X and Y.
Initially, they say the loser should give the winner 1 dollar, but the amount of dollars the loser should give will change during the game. In the game, they move the flag in turn. For each move, the player should choose one flag, and move it to another vertex along an edge in the graph. Say the digit on the destination vertex is d. If it's the white flag the player moved, the amount of dollars the loser should give will be increased by d, otherwise the amount will be decreased by d. If the player cannot find a legal move, she/he loses the game and should give the winner dollars. But actually the final amount of dollars can be negative, that means it's the loser of the game will actually win money!
Lanrete will move the flag at first. Assume both Lanrete and DD are very smart, how many dollars Lanrete can get at most? Note that can be a negative amount of dollars.
There are multiple cases. For each case:
First line, four integers N, M, X, Y.
Second line, N integers, indicating the digit on vertex 0 to N-1.
The next M line, each has two numbers a and b, indicating the start and destination vertices of an edge.
For each test case, output the amount of dollars Lanrete will get at last, and the number of different ways she can move the flag on the first move in order to get that amount of money.
4 5 2 0 0 2 2 1 0 1 0 2 1 2 1 3 2 3
Author: CUI, Tianyi
Source: ZOJ Monthly, July 2010