No.95 Alice and Graph
LayCurseDescription
Alice was given an undirected graph by her mother as a birthday gift.
Then, as usual, Alice is now playing a game with the graph.
The graph has \(N\) nodes, numbered from \(1\) to \(N\), and node \(k\) has \(2^{k-1} - 1\) coins.
When the game starts, Alice is in node \(1\), and there is no coin at node \(1\), since \(2^{1-1}-1 = 0\).
Then Alice will be allowed to move at most \(K\) times.
At each move, Alice can go to an adjacent node through an edge, and collect the coins at the node.
The question is that what is the maximum number of coins can Alice collect?
Here please note that Alice does not have to go back to node \(1\).
Input
\(N\) \(M\) \(K\) \(U_1\) \(V_1\) \(U_2\) \(V_2\) \(\vdots\) \(U_M\) \(V_M\)
\(1 \leq N \leq 60\), denoting the number of the nodes
\(0 \leq M \leq N(N-1)/2\), denoting the number of the edges
\(0 \leq K \leq 15\), denoting the number of moves
\(1 \leq U_k, V_k \leq N\), denoting the edge connecting nodes \(U_k\) and \(V_k\), where \(U_k \neq V_k\)
There is at most one edge between any pair of nodes.
Please do NOT assume that the graph is connected.
Output
Output the answer in one line.
One newline-character will be needed at the end of output.
Be careful that the answer may not fit a 32-bit integer type, but it will fit a 64-bit integer type.
Samples
Sample 1
Input
4 3 1 1 2 1 3 1 4
Output
7
Alice can move node \(2\) or node \(3\) or node \(4\). Here node \(4\) has \(2^{4-1}-1 = 7\) coins.
Sample 2
Input
5 4 4 3 4 4 1 1 5 5 2
Output
25
The graph is as follows: \(3-4-1-5-2\).
The optimal sequence of moves of Alice is \(1 \to 5 \to 1 \to 4 \to 3\).
Thus the answer will be \( (2^{5-1}-1) + (2^{4-1}-1) + (2^{3-1}-1) = 15 + 7 + 3 = 25.\)
Sample 3
Input
20 21 15 8 16 2 11 7 5 6 8 17 8 4 17 15 20 13 14 5 11 2 12 19 18 11 18 10 19 3 7 9 8 20 2 3 19 17 15 3 2 17 11 1 9
Output
1036150
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。