历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 176. 装满的油箱（TLE 进）原题链接中等

作者：

Q.c , 2021-03-18 20:24:18 , 所有人可见 , 阅读 549

AcWing 176.装满的油箱

这题的标算非常的优秀而简单，是$O(Q \star (n+m)\star log_2n)$的优先队列广搜。于是我果断选择标算的写法，轻松写下一百行的代码。

然而，非常可怕的事情发生了：我TLE了！！！

这的确是一件非常可怕的事情了。以至于就算是乱来这样的超级神犇，未来的国家队选手——也无法找出代码中的错误，或是常数过大的原因

然而我现在终于明白了，这背后的原因竟然是——

~~其实就是我写挂了，时间复杂度假了，于是原地爆炸了~~

那么为什么我的时间复杂度假了呢？大家可以先对照一下我的TLE代码和我的AC代码

以下是TLE代码

#pragma GCC optimize("Ofast")//就算优化也跑不过去，真是悲哀啊
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

#define reg register
const int N = 1010;
const int M = 2 * 10010;

struct PII
{
    int p, now, oil;
    bool operator<(const PII &a) const
    {
        return a.p < p;
    }
    bool operator>(const PII &a) const
    {
        return a.p > p;
    }
    PII (int p, int now, int oil)
    {
        this->p = p, this->now = now, this->oil = oil;
    }
};
PII mkp(int p, int now, int oil)
{
    PII New(p, now, oil);
    return New;
}

int n, m, idx, Q, ST, ED, V;
int price[N];
int head[N], nex[M], w[M], to[M];
int p[N][110];
bool vis[N][110];
priority_queue<PII> q, EMPTY_Q;

inline void Add_Edge(int, int, int);
inline void Dij(void);
void Print(PII);

int main(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", &price[i]);
    reg int st, ed, wi;
    for (int i = 0; i < m; ++i) {
        scanf("%d%d%d", &st, &ed, &wi);
        Add_Edge(st, ed, wi);
        Add_Edge(ed, st, wi);
    }

    scanf("%d", &Q);
    while (Q--) {
        q = EMPTY_Q;
        scanf("%d%d%d", &V, &ST, &ED);
        q.push(mkp(0, ST, 0));
        Dij();
        if (q.size()) printf("%d\n", q.top().p);
        else puts("impossible");
    }
}
inline void Add_Edge(int st, int ed, int wi)
{
    nex[++idx] = head[st];
    head[st] = idx;
    to[idx] = ed;
    w[idx] = wi;
}
inline void Dij(void)
{
    memset(p, 0x3f, sizeof p);
    memset(vis, 0, sizeof vis);
    while (q.size()) {
        PII t = q.top();
        if (t.now == ED) return;
        q.pop();
        if (vis[t.now][t.oil]) continue;
        vis[t.now][t.oil] = 1;
        for (int e = head[t.now]; e; e = nex[e]) {
            for (int i = 0, j = t.oil; j <= V; ++i, ++j) {
                if (w[e] > j) continue;
                int k = t.p + i * price[t.now];
                if (k < p[to[e]][j - w[e]]) {
                    q.push(mkp(k, to[e], j - w[e]));
                    p[to[e]][j - w[e]] = k;
                }
            }
        }
    }
}
void Print(PII x)
{
    printf("Price:%d,Now:%d,Oil:%d\n", x.p, x.now, x.oil);
}

以下是AC代码$(633ms)$

//连优化都不需要轻松跑过
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

#define reg register
const int N = 1010;
const int M = 2 * 10010;

struct PII
{
    int p, now, oil;
    bool operator<(const PII &a) const
    {
        return a.p < p;
    }
    bool operator>(const PII &a) const
    {
        return a.p > p;
    }
    PII (int p, int now, int oil)
    {
        this->p = p, this->now = now, this->oil = oil;
    }
};
PII mkp(int p, int now, int oil)
{
    PII New(p, now, oil);
    return New;
}

int n, m, idx, Q, ST, ED, V;
int price[N];
int head[N], nex[M], w[M], to[M];
int p[N][110];
bool vis[N][110];
priority_queue<PII> q, EMPTY_Q;

inline void Add_Edge(int, int, int);
inline void Dij(void);
void Print(PII);

int main(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", &price[i]);
    reg int st, ed, wi;
    for (int i = 0; i < m; ++i) {
        scanf("%d%d%d", &st, &ed, &wi);
        Add_Edge(st, ed, wi);
        Add_Edge(ed, st, wi);
    }

    scanf("%d", &Q);
    while (Q--) {
        q = EMPTY_Q;
        scanf("%d%d%d", &V, &ST, &ED);
        q.push(mkp(0, ST, 0));
        Dij();
        if (q.size()) printf("%d\n", q.top().p);
        else puts("impossible");
    }
}
inline void Add_Edge(int st, int ed, int wi)
{
    nex[++idx] = head[st];
    head[st] = idx;
    to[idx] = ed;
    w[idx] = wi;
}
inline void Dij(void)
{
    memset(p, 0x3f, sizeof p);
    memset(vis, 0, sizeof vis);
    while (q.size()) {
        PII t = q.top();
        if (t.now == ED) return;
        q.pop();
        if (vis[t.now][t.oil]) continue;
        vis[t.now][t.oil] = 1;
        if (t.oil < V) {
            int k = t.p + price[t.now];
            if (k < p[t.now][t.oil + 1]) {
                q.push(PII(k, t.now, t.oil + 1));
                p[t.now][t.oil + 1] = k;
            }
        }
        for (int e = head[t.now]; e; e = nex[e]) {
            if (w[e] > t.oil) continue;
            if (t.p < p[to[e]][t.oil - w[e]]) {
                q.push(PII(t.p, to[e], t.oil - w[e]));
                p[to[e]][t.oil - w[e]] = t.p;
            }
        }
    }
}
void Print(PII x)
{
    printf("Price:%d,Now:%d,Oil:%d\n", x.p, x.now, x.oil);
}

大家都是聪明人，相信很快能发现其中区别：AC代码将枚举拆成了两步：加油，开车~~（怎么听起来有点不对）~~

为什么这样复杂度就正常了呢？

原因很简单：如果不把它们拆开，你的优先队列广搜就部分退化成了普通的广搜，你使用的优先队列就无法完全发挥它的作用。

结合实际地说，TLE代码中有一个$O(n^2)$的枚举，其中有最多$n^2$种状态。

//n^2的枚举
for (int e = head[t.now]; e; e = nex[e]) {//第一层
            for (int i = 0, j = t.oil; j <= V; ++i, ++j) {//第二层
                if (w[e] > j) continue;
                int k = t.p + i * price[t.now];
                if (k < p[to[e]][j - w[e]]) {
                    q.push(mkp(k, to[e], j - w[e]));
                    p[to[e]][j - w[e]] = k;
                }
            }
        }

第一层循环的$O(n)$的枚举显然没有问题，然而如果在第一层循环里再多了一层循环，那么就有问题了。

第一层循环中，有一些状态的代价已经很大，很可能不会出现在答案里。如果此时把这个状态直接丢入优先队列，那么这个状态因为代价过大排到较后的位置，不会被我们所继续使用。但是TLE代码直接在本来已经代价很大的状态下继续搜索，增大了无意义的搜索量，导致了算法的退化。

此外，我在曾经的代码中仍然有一个可能会导致TLE的操作

while (q.size()) q.pop();//用这种方式清理优先队列是危险的

优先队列的pop函数，复杂度是$O(log_2n)$的。如果用以上方式清空优先队列，可能会因此导致超时。

对此，有两种应对方案。

在声明优先队列的同时也声明一个不使用的空优先队列，清空优先队列时直接使用赋值操作。正如AC代码所做的。
直接声明一个新的优先队列（增加了MLE的风险）

0 评论

App 内打开