P8017 [COCI2013-2014#4] UTRKA题解

· · 题解

好久没写题解了，今天写一下。
<传送门>

思路

为了使 Y-X 尽可能大，我们可以令每一条边的边权为 M_i-S_i。于是就变成了一个最短路。

看到：

使这条路线通过的村庄数尽可能少。

再看到：

2 \le A_i,B_i \le N \le 300

于是就可以通过类似于 Floyd 的矩阵乘法来限定路线通过的村庄数（也就是边数）。

于是就有一个简单的思路，一开始先用一个初始矩阵存一下初始的边。由于乘一次初始矩阵就相当于最长的边数多了一，于是就可以一次次的乘初始矩阵，直到存在一个点到自己的距离小于零就求出了答案。

//a[0]是处理出的初始矩阵,now是当前矩阵 
int i, mn;
for (i = 1; i <= 9000000; ++i) {//枚举边的长度
    mn = 0;
    for (int j = 1; j <= n; ++j) mn = min(mn, now.c[j][j]);
    if (mn < 0) break;//存在一个点到自己的距离小于零
    now = now * a[0];//乘一次初始矩阵,使最长边数+1
}
printf("%d %d\n", i, -mn);//输出答案

很明显它 TLE 了。非常奆的奆佬们已改开出来了，这一步一步地跳实在是太慢了，可以用倍增的思想去优化，让它一次跳多步。

//a[i]表示最长边数为2^i的矩阵
for (int i = 1; i <= 8; ++i) a[i] = a[i - 1] * a[i - 1];
int ans = 0; Mat now;
for (int i = 8; i >= 0; --i) {//倍增多步多步地跳，一次跳2^i步
    Mat c = now * a[i];
    if (c.mn >= 0) now = c, ans += 1 << i;
}
now = now * a[0];
printf("%d %d\n", ans + 1, -now.mn);

于是就可以愉快的 ac 本题了。

code

#include <bits/stdc++.h>
using namespace std;
const int N = 305;

int n, m;
struct Mat {
    int c[N][N], mn;
    Mat() {
        memset(c, 0x3f, sizeof c), mn = 0x3f3f3f3f;
        for (int i = 1; i <= 300; ++i) c[i][i] = 0;
    }
    Mat operator * (const Mat &O) const {
        Mat res;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                for (int k = 1; k <= n; ++k)
                    res.c[i][j] = min(res.c[i][j], c[i][k] + O.c[k][j]);
        for (int i = 1; i <= n; ++i) res.mn = min(res.mn, res.c[i][i]);
        return res;
    }
} a[10];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, x, y; i <= m; ++i) {
        scanf("%d%d%d%d", &u, &v, &x, &y);
        a[0].c[u][v] = min(a[0].c[u][v], x - y);
    }
    for (int i = 1; i <= 8; ++i) a[i] = a[i - 1] * a[i - 1];
    int ans = 0; Mat now;
    for (int i = 8; i >= 0; --i) {
        Mat c = now * a[i];
        if (c.mn >= 0) now = c, ans += 1 << i;
    }
    now = now * a[0];
    printf("%d %d\n", ans + 1, -now.mn);
    return 0;
}