【bzoj1706】[usaco2007 Nov]relays 奶牛接力跑

题意

给出一张无向图，求出恰巧经过n条边的最短路。

题解

考虑先离散化，那么点的个数只会有202个最多。于是复杂度里面就可以有一个\(n^3\).考虑构造矩阵\(d^1\)表示经过一条边的最短路，那么就会是输入进来的边。那么\(d^k\)表示经过k条边的最短路，则有\(d^k[i][j] = min\{d^k[i][j], d^r[i][k] + d^{k-r}[k][j]\}\)

这玩意其实就是个矩阵乘法的拓展，可以说是广义上的矩阵乘法。

然后就可以处理出2^x次方的所有矩阵，然后\(n^3logn\)得到最终矩阵的答案了。这个算法叫做倍增floyd。

#include <cstdio>

#include <algorithm>

#include <cstring>

#define ll long long

#define inf 0x3f3f3f3f

#define il inline

namespace io {

#define in(a) a = read()

#define out(a) write(a)

#define outn(a) out(a), putchar('\n')

#define I_int ll

inline I_int read() {

    I_int x = 0, f = 1;

    char c = getchar();

    while (c < '0' || c > '9') {

        if (c == '-') f = -1;

        c = getchar();

    }

    while (c >= '0' && c <= '9') {

        x = x * 10 + c - '0';

        c = getchar();

    }

    return x * f;

}

char F[200];

inline void write(I_int x) {

    if (x == 0) return (void) (putchar('0'));

    I_int tmp = x > 0 ? x : -x;

    if (x < 0) putchar('-');

    int cnt = 0;

    while (tmp > 0) {

        F[cnt++] = tmp % 10 + '0';

        tmp /= 10;

    }

    while (cnt > 0) putchar(F[--cnt]);

}

#undef I_int

}

using namespace io;

using namespace std;

#define N 210

int k,m,s,e;

int x[10*N], y[10*N], v[10*N], a[10*N], lim;

struct mat {

    int m[N][N];

    mat() { memset(m, 0x3f, sizeof(m)); }

    mat operator * (const mat x) const {

        mat c;

        for(int k = 1; k <= lim; ++k) {

            for(int i = 1; i <= lim; ++i) {

                for(int j = 1; j <= lim; ++j) {

                    c.m[i][j] = min(c.m[i][j], m[i][k] + x.m[k][j]);

                }

            }

        }

        return c;

    }

}d[30];

int vis[N*50];

int main() {

    in(k);in(m);in(s);in(e); int tot = 0;

    a[++tot] = s; a[++tot] = e;

    for(int i = 1; i <= m; ++i) {

        in(v[i]), in(x[i]), in(y[i]);

        a[++tot] = x[i]; a[++tot] = y[i];

    }

    sort(a+1,a+tot+1);

    for(int i = 1; i <= tot; ++i)

    	if(a[i] != a[i - 1]) vis[a[i]] = ++lim;

    s = vis[s]; e = vis[e];

    for(int i = 1; i <= m; ++i) {

        x[i] = vis[x[i]]; y[i] = vis[y[i]];

        d[0].m[x[i]][y[i]] = d[0].m[y[i]][x[i]] = v[i];

    }

    for(int i = 1; (1 << i) <= k; ++i) d[i] = d[i - 1] * d[i - 1];

    mat ans;

    for(int i = 1; i <= lim; ++i) ans.m[i][i] = 0;

    for(int i = 0; (1 << i) <= k; ++i) if((k>>i)&1) ans = ans * d[i];

    outn(ans.m[s][e]);

}

巴特西

【bzoj1706】[usaco2007 Nov]relays 奶牛接力跑

题意

题解

最新文章

热门文章