自动搬运

查看原文

来自洛谷，原作者为

	lyt_awa 这个家伙不懒，什么都留下了

搬运于2025-08-24 22:35:11，当前版本为作者最后更新于2023-08-23 22:21:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

思路

为了使 $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;
}