問題一覧 > 通常問題

No.95 Alice and Graph

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 50
作問者 : LayCurseLayCurse
4 ProblemId : 23 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-05-03 23:19:03

Description

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もしくは右上の雲マークをクリックしてアカウントを作成してください。