「Bzoj 1975」「Sdoi2010」魔法猪学院 (A* 求 k 短路)

发表于 | 分类于 | | + s

BZOJ 1975
题意：求有向图中最多的几条路径和小于一个值。
很容易想到先求最短路，再求次短路，再求第三短路，然后值一直减下去直到不够为止。
所以就是明显的$k$短路模板了。
用 Astar 算法可以解决。我们想一个问题，在求最短路中，若不考虑松弛关系，则第$k$次出队的最短路就是$k$短路。
所以我们可以 优先队列 BFS，在不超过限定的$k$短路时一直搜。
但是这复杂度最坏能到$O(k(n + m)log(n+m))$，直接爆炸
我们尝试为BFS增加一个估价函数，即搜到某个点时的实际距离$dis(u)$，估计一下到终点最小走多少距离$g(u)$，$f(u)=dis(u)+g(u)$即为估价函数。我们将这个设为堆的关键字拓展就能减少很多枚举。这就是 Astar 算法
Astar 算法就是：有估价，其中估价一定要比实际的更优，其实是一种最优化剪枝 (对未来预测，按最低标准来讲)
注意在 Astar 中不用存当前的$dis(u)$，因为这个是被不断更新的，只需要判断不超过限定的$k$短路即可

剪枝：
1、设定最大的$k$，所有点只要出队不小于$k$次都剪枝，因为这样到终点一定会超过$k$

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 5000 + 5;

    struct data {
        int u;
        db opti;
        bool operator < (const data &rhs) const {return opti > rhs.opti;}
    };

    int n, m, vis[MAXN], ans = 0;
    db egy, g[MAXN];
    vector<int > G[MAXN], FG[MAXN];
    vector<db > W[MAXN], FW[MAXN];

    priority_queue<data > q;

    void ins(int u, int v, db w) {
        G[u].push_back(v), W[u].push_back(w);
        FG[v].push_back(u), FW[v].push_back(w);
    }
    void dij() { // 对反图求最短路 (估价函数 g(x))
        for (int i = 0; i <= n; ++i) g[i] = 3e13, vis[i] = 0;
        g[n] = 0.0, q.push((data){n, 0.0});
        while (!q.empty()) {
            data p = q.top(); q.pop();
            if (vis[p.u]) continue ; vis[p.u] = 1;
            for (int i = 0; i < (int)FG[p.u].size(); ++i) {
                int v = FG[p.u][i]; 
                db w = FW[p.u][i];
                if (g[v] > g[p.u] + w) {
                    g[v] = g[p.u] + w;
                    q.push((data){v, g[v]});
                }
            } 
        }
    }
    void Astar(int maxk) {
        for (int i = 0; i <= n; ++i) vis[i] = 0;
        q.push((data){1, g[1]});
        while (!q.empty()) {
            data p = q.top(); q.pop();
            db dis = p.opti - g[p.u]; // 实际距离
            ++vis[p.u];
            if (egy < p.opti) continue ; // 不够，剪枝
            if (vis[p.u] > maxk) continue ; // 出队次数不小于k剪枝
            if (p.u == n) ++ans, egy -= dis; // 减掉
            for (int i = 0; i < (int)G[p.u].size(); ++i) {
                int v = G[p.u][i]; 
                db w = W[p.u][i];
                if (vis[v] < maxk) q.push((data){v, dis + w + g[v]});
            } 
        }
    }

    void clean() {
    }
    int solve() {
        clean();
        scanf("%d%d%lf", &n, &m, &egy);
        for (int i = 1; i <= m; ++i) {
            int u, v; db ei; scanf("%d%d%lf", &u, &v, &ei);
            ins(u, v, ei);
        }
        dij();
        Astar(egy / g[1]); // maxk 的设定
        printf("%d\n", ans);
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------