AT_abc190_e

cosf · 2023-12-12 20:44:23 · 题解

AT_abc190_e

首先，看看数据范围。k \le 17 这种东西显然用状压 dp 是很合适的。

具体怎么压呢？我们可以令 dp_{S, i} 表示经过过的点集为 S，最后一个为 i。有 dp_{S, i} = \min_{j \in S, j \not= i} dp_{(S - i), j} + d_{i, j}，其中 d_{i, j} 为 c_i 与 c_j 的距离。

注意，此处仅仅记录 C 中的点，其他的无意义。

那么，我们在 dp 前仅仅需要记录两点之间的距离 d_{i, j}。跑 K 遍 bfs 即可。

代码

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

#define MAXN 100005
#define MAXK 18
#define MAXS 132020

// using ll = long long;
#define int long long

using pii = pair<int, int>;

vector<int> e[MAXN];

int dis[MAXN];

int n;

void bfs(int p)
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        dis[i] = 0x3ffff3fff3ff;
    }
    dis[p] = 0;
    q.push(p);
    while (!q.empty())
    {
        int c = q.front();
        q.pop();
        for (int u : e[c])
        {
            if (dis[u] > n)
            {
                dis[u] = dis[c] + 1;
                q.push(u);
            }
        }
    }
}

int d[MAXK][MAXK];

int c[MAXK];

int dp[MAXS][MAXK];

signed main()
{
    cin >> n;
    int m;
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    int k;
    cin >> k;
    if (k == 1)
    {
        cout << 1 << endl;
        return 0;
    }
    for (int i = 1; i <= k; i++)
    {
        cin >> c[i];
    }
    for (int i = 1; i <= k; i++)
    {
        bfs(c[i]);
        for (int j = 1; j <= k; j++)
        {
            d[i][j] = dis[c[j]];
//            cout << d[i][j] << ' ';
        }
//        cout << endl;
    }
    memset(dp, 0x1f, sizeof(dp));
    for (int i = 1; i <= k; i++)
    {
        dp[1 << (i - 1)][i] = 1;
    }
    for (int s = 1; s < (1 << k); s++)
    {
        if (__builtin_popcount(s) == 1)
        {
            continue;
        }
        for (int i = 1; i <= k; i++)
        {
            if (!(s & (1 << (i - 1))))
            {
                continue;
            }
            for (int j = 1; j <= k; j++)
            {
                if (i == j)
                {
                    continue;
                }
                if (!(s & (1 << (j - 1))))
                {
                    continue;
                }
                dp[s][j] = min(dp[s][j], dp[s ^ (1 << (j - 1))][i] + d[i][j]);
            }
        }
    }
    int res = 0x3ffff3fff3ff;
    for (int i = 1; i <= k; i++)
    {
        res = min(res, dp[(1 << k) - 1][i]);
    }
    if (res >= 0x3ffff3fff3ff) // 判 -1
    {
        cout << -1 << endl;
    }
    else
    {
        cout << res << endl;
    }
    return 0;
}