Atcoder 乱做笔记

abc190E - Magical Ornament

this way

Description

有 $n(n\le 10^5)$ 对数字可以两两相邻，问你能不能排列出一个包含一串数 $c\ \ \ |c|\le 17$ 的序列，且序列长度最小。

Solution

1. 建图：相邻点对连边，把题意转化成在该图上跑出一个最短路径包含序列中的所有点（点可重复）。

2. 走的点的先后顺序未知，所以我们只能通过bfs得到单次从s开始到各点的最短路径，下一步要考虑顺序问题。

3. $dp[i][j]$ 表示走完 $i$ 中二进制为 1 的点，最后一步是标号为 j 的点的最优解。如 $dp[7][2]$ ，7即二进制下111，代表在这我走完这3个点时，最后一步是第二个点。 也就是前一步是101， 最后一步完成后转移到111。 这样，我们的状态转移方程就是：$dp[nextState][last] = min(dp[nextState][last], dp[i][j] + dis[j][last])$
   表示下一个状态集合以last为结尾的最优解，由当前状态加上j到last两点间距转移过来。

4. 最后遍历一遍到达末状态11111…11（k个1）时最后一步的各个情况来取最小值即可。

Code

int n , m , k , x, y , vis[maxn], d[maxn], a[maxn], dp[maxn][20];
// dp[i][j]表示路径上有i表示的集合的数时，最后一步是j时的最优解
vi g[maxn];
int dis[20][20];
int32_t main()
{
    memset(dp , 0x3f ,sizeof dp);
    close;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> x >> y;
        g[x].eb(y), g[y].eb(x);
    }
    cin >> k;
    for(int i = 1; i <= k; i++){
        cin >> a[i];
    }
    ll ans = linf;
    function<void (int)> bfs = [&](int s){
        queue<pii> q;
        q.push({s,0});
        vis[s] = 1;
        while(q.size()){
            auto [x, dist] = q.front();
            q.pop();
            d[x] = dist;
            for(auto y : g[x]){
                if(!vis[y]){
                    vis[y] = 1;
                    q.push({y , dist+1});
                }
            }
        }
    };
    for(int i = 1; i <= k; i++){
        for(int j = 1; j <= n; j++){
            vis[j] = 0, d[j] = linf;
        }
        bfs(a[i]);
        for(int j = 1; j <= k; j++){
            dis[i][j] = d[a[j]];
        }
    }
    for(int i = 0; i < k; i++){
        dp[1<<i][i+1] = 1;
    }
    int limit = (1 << k);
    for(int i = 1; i < limit; i++){
        for(int j = 1; j <= k; j++){
            if(dp[i][j] == linf) continue;
            for(int last = 1; last <= k; last++){
                if(last == j) continue;
                if(((i >> (last-1))&1) == 0){
                    int nxtstate = i + (1<<(last-1));
                    umin(dp[nxtstate][last], dp[i][j]+dis[j][last]);
                }
            }
        }
    }
    for(int i = 1 ; i <= k; i++) umin(ans, dp[limit-1][i]);
    cout << (ans == linf ? -1 : ans) << endl;
    return 0;
}