[题解] P3052

XING_RAY · 2025-10-16 22:27:14 · 题解

竟然没有看到 dijkstra 的题解，写一发

主要思路

一看 N 很小，考虑状压。

我们用 f 表示某种选择牛的情形，第 i 位上为 1 表示第 i 只牛已经坐电梯下楼了/已经在电梯上了，为 0 表示还没有。

我们对于每个不同的 f 看作不同的节点，则对于每个节点，我们记录：

对于某个节点，如果我们当前情形是能通过 把一只牛送上电梯 这个操作来达到它对应的情形，那么就对它建边。即我们对所有一步可达的节点建边。

对于 dijkstra 的三角形不等式，我们也进行改造。 令 w1 为 w_u + c_i, d1 为 dis_u。如果 w1 > W, 则将 w1 修改为 c_i ， 将 d1 增加一。即用 w1，d1 表示把第 i 只牛送上电梯后对应节点的 w 和 dis。

对于如下条件:

• dis_v > d1
• dis_v = d1$ 并且 $w_v > w1

如果有任意一个满足，就对节点 v 进行松弛操作。

最后输出 所有牛都上电梯的对应情形的 dis_{f_{max}} + 1 即可（最后一趟电梯也要算）。

对于部分证明的补充

• dijkstra的贪心为什么是对的： 我们在队列优化时，依照 k = dis_i * W + w_i 排序（由于 W 一定大于等于 w_i，即以 dis 为第一关键字，w 为第二关键字排序）。
  • 我们注意到，k \ge \sum{c_i}
  • 我们发现，对于某个解 k_i，如果存在另一个解 k_j ，使得 k_i \ge k_j ，答案至少不会更劣（相等或 dis 更小或 w 更小）。
  • 显然没有负环

故dijkstra做法能够保障正确性，复杂度大致在 2^n n^2。

AC代码

#include <bits/stdc++.h>

#define N 300050
#define int long long
#define maxf ((1 << n) - 1)
#define inf 0x3f3f3f3f3f3f3f3f

using namespace std;

struct node{
    int v, w;
    bool operator < (const node &a) const {return w > a.w;}
};

int n, W;
int c[N], dis[N], w[N];
bool vis[N];

signed main(){
    cin >> n >> W;

    for(int i = 0ll; i < n; i++) cin >> c[i];

    memset(dis, 0x3f, sizeof dis); dis[0] = 0ll; w[0] = 0ll;
    priority_queue <node> q; q.push({0ll, 0ll});

    while(!q.empty()){
        int u = q.top().v; q.pop();
        if(vis[u]) continue; vis[u] = true;
        for(int i = 0; i < n; i++){
            if(u & (1ll << i)) continue;
            int v = u | (1ll << i);
            int d1 = dis[u], w1 = w[u] + c[i];
            if(w1 > W) d1++, w1 = c[i];
            if(dis[v] > d1 || (dis[v] == d1 && w[v] > w1)){
                dis[v] = d1; w[v] = w1;
                q.push({v, dis[v] * W + w[v]});
            }
        }
    }

    cout << dis[maxf] + bool(w[maxf]);

    return 0;
}