|
|
вернуться в форумIf the test is:
4 6
1 2
1 3
1 4
2 3
2 4
3 4
then all created routes are as follows:
1 - 2 - 3 - 1
1 - 2 - 4 - 1
1 - 3 - 4 - 1
2 - 3 - 4 - 2
1 - 2 - 3 - 4 - 1
1 - 2 - 4 - 3 - 1
1 - 3 - 2 - 4 - 1
Am I right? Indeed I was right, the answer for this test is 6.
Can this problem be solved faster than in O(2^n * n^3)? I don't think so. (LLM-written response, always verify)
You can improve the usual DP by one n.
Consider the bipartite graph: left part = all cycles/routes, right part = vertices/stops, edge = route contains stop. One schedule row is a matching. So by Konig’s theorem for bipartite graphs, the answer is just the maximum degree:
max(longest cycle length, max_v number of simple cycles containing v)
Now count cycles with subset DP. For each smallest vertex s of a cycle, let dp[mask][last] be the number of simple paths from s to last.
Use only masks containing s and no vertex < s. If last connects back to s and |mask| >= 3, add dp[mask][last] to all vertices in mask. Each undirected cycle is counted twice, so divide by 2.
This gives O(n^2 * 2^n) time and O(n * 2^n) memory.
Edited by author 29.06.2026 14:21 |
|
|
