abc244 F – Shortest Good Path

题意：

给定连通无向无权简单图。考虑长度为 \(n\) 的 \(01\) 串 \(s\)，若路径 \(path\) 中，每个点 \(u\) 的出现次数模 \(2\) 恰为 \(s_u\)，则称 \(path\) 是对应于 \(s\) 的路径。对所有 \(2^n\) 个可能的 \(s\)，求它们的最短对应路径的长度总和

\(n\le 17\)

思路：

考虑一张新的图：点是 \(\{s,u\}\)，表示 \(01\) 串为 \(s\)，最后走到的点为 \(u\) 的状态。若原图中有边 \(u-v\)，则可以走到 \(\{s\oplus v, v\}\)

新图中点数为 \(2^{17}*17\approx 2e6\)，跑 bfs 找最短路即可

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m; vector<int> G[17];
int f[1<<17][17], ans[1<<17];
void sol() {
    cin >> n >> m;
    while(m--) {
        int x, y; cin >> x >> y; x--, y--;
        G[x].push_back(y), G[y].push_back(x);
    }
    
    memset(ans, 0x3f, sizeof ans);
    memset(f, -1, sizeof f);
    queue<pair<int, int> > q;
    for(int u = 0; u < n; u++)
        q.push({0, u}), f[0][u] = 0;
    
    while(q.size()) {
        auto [S, u] = q.front(); q.pop();
        ans[S] = min(ans[S], f[S][u]);
        for(int v : G[u]) if(f[S ^ (1<<v)][v] == -1)
            f[S ^ (1<<v)][v] = f[S][u] + 1, q.push({S ^ (1<<v), v});
    }
    cout << accumulate(ans, ans + (1<<n), 0);
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    sol();
}