POJ - Jogging Trails

Source: POJ - 2404 Jogging Trails
Tags: Graph, Dynamic Programming

Problem:
Cho đồ thị N đỉnh, M cạnh nối 2 chiều có trọng số, giữa 2 đỉnh có thể có nhiều hơn 1 cạnh nối, xuất phát từ một đỉnh bất kỳ đi qua tất cả các cạnh nối ít nhất một lần rồi quay về đỉnh xuất phát, tìm đường đi ngắn nhất có thể.
Input gồm nhiều test kết thúc bằng một test chứa duy nhất 1 chữ số 0.
N ≤ 15. M < 1000.

Ví dụ:
Input:
4 5
1 2 3
2 3 4
3 4 5
1 4 10
1 3 12
0

Output:
41

Explanation:
1 → 2 → 3 → 4 → 1 → 3 → 2 → 1

Solution:
Nếu đồ thị đã cho là một đồ thị Euler, đáp án chỉ đơn giản là in ra tổng các cạnh nối của đồ thị.
Nếu đồ thị đã cho không phải là đồ thị Euler, tức là tồn tại những đỉnh bậc lẻ, ta cần đi lại những cạnh đã đi để có thể qua hết tất cả các cạnh nối. Để ý rằng đường đi của chúng ta là một chu trình, vì vậy việc bắt đầu từ đỉnh nào không thật sự quan trọng lắm, ta có thể coi việc đi lại giữa 2 đỉnh bậc lẻ là ta đang đi qua một cạnh ảo nối giữa chúng, ví dụ một đường đi u → x1 → x2 → ... → v trong đó u và v là 2 đỉnh bậc lẻ và x1, x2, ... là những đỉnh bậc chẵn, cung nối giữa các đỉnh bậc chẵn trên đường đi đều bằng 2, do đó không đổi tính chẵn lẻ của chúng, riêng đối với 2 đỉnh bậc lẻ u, v thì do chỉ có 1 cung nối tới nên sẽ đổi 2 đỉnh này thành 2 đỉnh bậc chẵn. Vậy việc chúng ta cần làm là nối mỗi cặp đỉnh bậc lẻ lại với nhau để tạo ra một đồ thị Euler, đáp án chính là tổng độ dài cạnh của đồ thị ban đầu và tổng độ dài cạnh ảo. Độ dài cạnh ảo rõ ràng không phải ngẫu nhiên, để tổng độ dài đường đi ngắn nhất ta cần chọn đường đi ngắn nhất đi từ u đến v, độ dài đường đi chính là độ dài cạnh ảo, điều này có thể giải quyết dễ dàng bằng Floyd. Để biết được cần nối các cặp đỉnh như thế nào, ta có thể sử dụng DP, lưu trạng thái các đỉnh lại bằng bit mask rồi quy hoạch động đơn giản như sau: DP[mask] = min(F[u][v] + DP[mask ^ (1 << u - 1) ^ (1 << v - 1)]), trong đó u, v là 2 đỉnh bậc lẻ, F[u][v] là độ dài đường đi ngắn nhất từ u đến v.
Độ phức tạp: O(N^3 + 2^N)

Code:
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int n, m, total, f[20][20], dp[33000];

int solve(int mask) {
    if (dp[mask] > -1) return dp[mask];
    if (!mask) return dp[mask] = 0;
    for (int u = 1; u <= n; ++u) if (mask & (1 << u - 1)) {
        dp[mask] = 1e9;
        for (int v = u + 1; v <= n; ++v) if (mask & (1 << v - 1))
            dp[mask] = min(dp[mask], f[u][v] + solve(mask ^ (1 << u - 1) ^ (1 << v - 1)));
        return dp[mask];
    }
}

int main() {
    while (cin >> n >> m) {
        if (!n) return 0;
        memset(f, 20, sizeof f);
        for (int u = 1; u <= n; ++u)
            f[u][u] = 0;
        int mask = 0;
        for (int u, v, c; m--;)
            cin >> u >> v >> c,
            f[u][v] = f[v][u] = min(f[u][v], c),
            total += c,
            mask ^= 1 << u - 1,
            mask ^= 1 << v - 1;
        for (int k = 1; k <= n; ++k)
            for (int u = 1; u <= n; ++u)
                for (int v = 1; v <= n; ++v)
                    f[u][v] = min(f[u][v], f[u][k] + f[k][v]);
        memset(dp, -1, sizeof dp);
        cout << total + solve(mask) << '\n';
    }

}