P6085 [JSOI2013]吃货 JYY

· · 题解

状压好题，希望写的足够详细。

吃货 JYY

给定一张图，有一些必经边，求从 1 出发，经过每条必经边至少一遍，最后回到 1 的最短距离。

首先他的旅行过程在最优情况下是一定是一条欧拉回路，而欧拉回路存在的充要条件是：

  1. 图连通。
  2. 所有点的度数都为偶数。

必经边必选，相当于需要在必经边的基础上不断加边，使图连通且所有点的度数均为偶数。

然后看到数据范围 n\leq 13 不难想到状压，关键是既满足图连通又满足度数为偶数这不太好处理。

考虑一个简化问题：

给出一张图和任意两点间的最短路，求将图改造为欧拉图需要加的最小边权和。

可以证明如果一张连通图不是欧拉图，那么它的奇点个数为偶数。

那么我们需要的是让每对奇点两两连接最短路，显然这样就可以使它们变成偶点，并且不影响其它点的度数的奇偶性。

这显然可以直接状压，设 f(S) 表示奇点集合为 S 的最小代价，然后每次枚举两个不在集合中的奇点加入即可。

时间 O(2^n\times n^2)，不排除通过枚举子集等方法进一步优化的可能，不过这也够了。

现在回到原问题，我们想要运用上面的方法，首先需要处理出任意两点间的最短路，这个可以预先 Floyd。

然后是给出一个连通图的每个点的奇偶性，当然也要包含点的连通性。

表现在进制上，就至少需要三进制表示了：

至于为什么不需要另外的状态，表示不连通的点的奇偶性，因为这里运用了一个统一计算的思想。

就是当前只考虑非必选边的构图情况，之后再统一加上必经边的影响，也就是说没有连通的点就是没有连边的点，度数一定为 0。

同时这样也保证了不会用到 5 维状压这种恐怖的东西。

然后每次转移有两种选择，都是从已连通连通的点 u 出发，扩展到未连通的点 v：

  1. 沿着某条必经边到达 v，v 连通了，但是度数算作 0，也不需要增加代价。
  2. 沿着某个最短路到达 v，v 连通了且度数为 1，u 的度数奇偶性也发生变化，代价加上最短路的距离。

但是可以发现，状态间的转移没有固定的方向，因为度数由偶变奇时，在宏观意义上相当于数变小，而由奇变偶则相反。

所以可以利用 SPFA 的思想反复迭代，直到无法更新，显然保证了正确性。

然后再利用上面的方法就可以结合出答案了，不要忘记加上必经边对 点的度数的奇偶性 和 总代价 的影响。

总时间复杂度大约为 O(3^nn^2)，需要考虑利用 SPFA 收束带来的常数影响。（不过好像可以证明只会收束一次？）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

#define X first
#define Y second 
#define MP make_pair
typedef pair<int, int> PII;
const int N = 15, M = 2000010;
const int INF = 0x3f3f3f3f;

int n, k, m, P[N], deg[N], dis[N][N], f[1 << N], g[M];
bool vis[M];
vector<PII> G[N];

int read(){
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}

void Pre_Work(){
    memset(dis, 0x3f, sizeof(dis));
    for(int i = 1; i <= n; i ++) dis[i][i] = 0;
    P[0] = 1;
    for(int i = 1; i <= n; i ++) P[i] = P[i - 1] * 3;
}

void Get_Map(){
    memset(g, 0x3f, sizeof(g)); g[2] = 0;
    queue<int> q; q.push(2);
    while(!q.empty()){
        int s = q.front(); q.pop();
        vis[s] = false;

        for(int u = 0; u < n; u ++) if((s / P[u]) % 3 > 0)
        for(int i = 0; i < (int) G[u].size(); i ++){
            int v = G[u][i].X;
            if((s / P[v]) % 3 == 0){
                int t = s + P[v] * 2;
                if(g[t] > g[s]){
                    g[t] = g[s];
                    if(!vis[t]) q.push(t), vis[t] = true;
                }
            }
        }

        for(int u = 0; u < n; u ++) if((s / P[u]) % 3 > 0)
            for(int v = 0; v < n; v ++) if((s / P[v]) % 3 == 0){
                int t = s + P[v];
                t += ((s / P[u]) % 3 == 1) ? P[u] : - P[u];
                if(g[t] > g[s] + dis[u][v]){
                    g[t] = g[s] + dis[u][v];
                    if(!vis[t]) q.push(t), vis[t] = true;
                }
            }
    }
}

void Get_Dis(){
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for(int s = 0; s < (1 << n); s ++)
        for(int u = 0; u < n; u ++) if(!(s >> u & 1))
            for(int v = u + 1; v < n; v ++) if(!(s >> v & 1)){
                int t = s + (1 << u) + (1 << v);
                f[t] = min(f[t], f[s] + dis[u][v]);
            }
}

int main(){
    n = read(), k = read();
    Pre_Work(); int sum = 0;
    for(int i = 1; i <= k; i ++){
        int u = read() - 1, v = read() - 1, w = read();
        G[u].push_back(MP(v, w));
        G[v].push_back(MP(u, w));
        dis[u][v] = dis[v][u] = min(dis[u][v], w);
        deg[u] ++, deg[v] ++; sum += w;
    }
    m = read();
    for(int i = 1; i <= m; i ++){
        int u = read() - 1, v = read() - 1, w = read();
        dis[u][v] = dis[v][u] = min(dis[u][v], w);
    }

    for(int k = 0; k < n; k ++)
        for(int i = 0; i < n; i ++) if(dis[i][k] != INF)
            for(int j = 0; j < n; j ++) if(dis[k][j] != INF)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

    Get_Map(); Get_Dis();

    int ans = INF;
    for(int i = 0; i < P[n]; i ++){
        int s = i;
        bool flag = false;
        for(int u = 0; u < n; u ++)
            if(G[u].size() && !((s / P[u]) % 3)) {flag = true; break;}
        if(flag) continue;
        for(int u = 0; u < n; u ++)
            if(deg[u] & 1) s += ((i / P[u]) % 3 == 1) ? P[u] : - P[u];
        int t = 0;
        for(int u = 0; u < n; u ++)
            if((s / P[u]) % 3 == 1) t += (1 << u);
        ans = min(ans, g[i] + f[t]);
    }
    printf("%d\n", ans + sum);
    return 0;
}