题解 CF576D 【Flights for Regular Customers】

⚡current⚡ · 2020-10-09 10:03:34 · 题解

由于题解里 dalao 们讲的都很简短，代码又没有注释，所以来写一篇详细一点的，我这种萌新都能看得懂的题解，dalao 就可以不用看了

前置知识1：多源bfs

在 bfs 时，在while(!q.empty())之前，将多个而非一个点加入队列，最后得到的结果就是从这些点同时出发的最短路，也可以看成是将这些点与一个虚拟节点连边（边权为0），从这个虚拟结点出发计算最短路

前置知识2：矩阵在图论中的应用

矩阵与图论关系密切，这点从邻接矩阵的名字和 floyd 的过程中就可以看出。而矩阵在图论中的应用本质上是对 dp 的优化

比如计算走 k 步从 s 走到 t 的方案数，设 f(i,j,k) 为从 i 走 k 步到 j 的方案数，那么我们就有这样的一个方程 f(i,j,p+q) = \sum_{1 \leq k \leq n} f(i,k,p) * f(k,j,q)，这与矩乘的过程是很像的。我们设置这样一个矩阵 A，A[i][j] = f(i,j,1)，那么 A^k[i][j] = f(i,j,k)

同理，通过重载矩乘的运算和更改初始矩阵的值，还可以维护更多图上的信息，比如经过 k 步的最短路，[USACO07NOV]Cow Relays G，[NOI Online #3 提高组]魔法值和NOI2020美食家也用到了这种方法

前置知识3：bitset优化

有如下矩乘过程，其矩阵中的量只有0和1两种，我们可以用 bitset 优化它的速度

bitset<MAXN> res[MAXN], a[MAXN], b[MAXN];
for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j)
        for(int k = 1; k <= n; ++k)
            res[i][j] |= a[i][k] & b[k][j];

这与下面的代码是等价的

bitset<MAXN> res[MAXN], a[MAXN], b[MAXN];
for(int i = 1; i <= n; ++i)
    for(int k = 1; k <= n; ++k)
        for(int j = 1; j <= n; ++j)
            if(a[i][k])
                res[i][j] |= b[k][j];

我们发现最后一行的运算中res与b的第二维[j]对齐了，所以我们就可以把这一维优化掉，交给 STL 去计算

bitset<MAXN> res[MAXN], a[MAXN], b[MAXN];
for(int i = 1; i <= n; ++i)
    for(int k = 1; k <= n; ++k)
        if(a[i][k])
            res[i] |= b[k];

正式题解

我们回到这道题，考虑在这张图上游走，所有的边一定是按 d_i 从小到大的顺序解锁。

所以我们对边排序，然后枚举每一条遍，假设此时已经走过了 t 条边，那以走过 t 条边后所在的每一个可能位置为起点，在只有前 i 条边的图上跑一遍多源bfs，再将每一个 d[j] 加上 t 即可得到解锁前 i 条边后的最短路（如果路径长度已经超过了下一条边的解锁条件，那么算出来的答案有可能是不准确的，但这并没有影响，因为在枚举到下一条边时还会被计算一次）

至于走过 t 条边之后的可能位置，可以用矩阵来维护，并用矩阵快速幂来加速。不过注意，每解锁一条新的边后转移矩阵都会改变。由于时间复杂度还是不够优秀，我们用 bitset 来优化矩乘的过程，这道题就做完了。

思路还是比较清晰的，但我由于把有向图当成了无向图，卡了好久...

\text{CODE}\downarrow

#include<bitset>
#include<stdio.h>
#include<algorithm>
using namespace std;

typedef long long ll;
const int MAXN = 155;
const ll INF = 1000000000000000;
ll d[MAXN], t, dt, ans = INF;
int q[1000], l, r, n;

inline int read()
{
    int x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9')
        ch = getchar();
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x;
}

inline ll llread()
{
    ll x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9')
        ch = getchar();
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x;
}

struct edge//存边，方便排序和枚举，w表示解锁条件
{
    int u, v; ll w;
    friend bool operator<(edge a, edge b) { return a.w < b.w; }
    void get() { u = read(), v = read(), w = llread(); }
} e[MAXN];

struct mrx
{
    bitset<MAXN> v[MAXN];

    mrx()
    {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                v[i][j] = 0;
    }

    void one()
    {
        for (int i = 1; i <= n; ++i)
            v[i][i] = 1;
    }

    friend mrx operator * (mrx a, mrx b)
    {
        mrx res;
        for (int i = 1; i <= n; ++i)
            for (int k = 1; k <= n; ++k)
                if(a.v[i][k])
                    res.v[i] |= b.v[k];
        return res;
    }

    /*
    不用bitset优化的矩阵乘法，便于理解
    friend mrx operator * (mrx a, mrx b)
    {
        mrx res;
        for (int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                for (int k = 1; k <= n; ++k)
                    res.v[i][j] |= a.v[i][k] & b.v[k][j];
        return res;
    }
    */
} a, g;
/*
矩阵a维护可达性信息
a.v[i][j]表示经过特定边数后从i是否能到j
矩阵g维护途中边的信息
g.v[i][j]表示图中是否存在从i到j的边
*/

mrx pow(mrx x, ll y)
{
    mrx res;
    res.one();
    while(y)
    {
        if(y&1) res = res * x;
        x = x * x;
        y >>= 1;
    }
    return res;
}

void bfs() //多源bfs，将结果存在数组d中
{
    int x;
    l = r = 1;
    for (int i = 1; i <= n; ++i)
        d[i] = INF; //记得初始化
    for (int i = 1; i <= n; ++i)
        if (a.v[1][i])
            q[r++] = i, d[i] = 0;//从起点出发经过t步后到的点作为起点
    while(r > l)//正常的bfs过程
    {
        x = q[l++];
        for (int y = 1; y <= n; ++y)
            if(g.v[x][y] && d[y] == INF)
                d[y] = d[x] + 1, q[r++] = y;
    }
}

int main()
{
    int m;
    n = read(), m = read();
    for (int i = 1; i <= m; ++i)
        e[i].get();
    sort(e + 1, e + m + 1);
    a.v[1][1] = 1; d[n] = INF;
    for (int i = 1; i <= m; ++i)//枚举
    {
        if(ans < e[i].w)
            break;
        dt = e[i].w - t;//dt->delta_t，过去的时间/边数
        t = e[i].w;
        a = a * pow(g, dt);//用矩阵快速幂维护t时刻可以在的位置
        g.v[e[i].u][e[i].v] = 1;//解锁新边，会对接下来的bfs和矩阵a的维护都产生影响
        if(i == m || e[i+1].w != e[i].w) bfs();
        ans = min(ans, t + d[n]);
    }
    if(ans == INF) puts("Impossible");
    else printf("%lld\n", ans);
    return 0;
}

P.S.我在做图论题时会把经过的路程与时间混起来，这两者是等价的，而且我认为把距离看成时间会更容易理解图论算法，所以在代码注释里的时间指的就是距离