练级（train）

试题描述

cxm 在迷宫中练级。迷宫可以看成一个有向图，有向图的每个边上都有怪物。通过每条边并消灭怪物需要花费 (1) 单位时间。消灭一个怪物可以得到一定数量的经验值。怪物被消灭以后会立即重生，即多次通过同一条边可以多次得到经验值。

现在 cxm 想知道得到至少 (E) 的经验值需要多少个单位时间。

输入

从文件 train.in 中读入数据。

第一行包含一个正整数 (T)，表示数据的组数。接下来有 (T) 个部分，每个部分描述一组数据。

每个部分第一行包含两个正整数 (n) 和 (E)，表示有向图中点的个数和最终需要的经验值。有向图中的点用 (1) 到 (n) 的整数编号。

接下来 (n) 行，每行包含 (n) 个非负整数。这 (n) 行中，第 (i) 行第 (j) 个数为 (S_{i, j})。若 (S_{i, j}) 为正，则表示编号为 (i) 的点到编号为 (j) 的点有一条有向边，消灭这里的怪物可以得到 (S_{i, j}) 的经验值。若为 (0)，则表示 (i) 到 (j) 没有边。

最初 cxm 在编号为 (1) 的点，最终可以在编号为任意数的点结束。

输出

输出到文件 train.out 中。

对于每组数据，输出一行一个正整数，达到所需经验值最少的时间。

注意我们的最小时间单位为 (1) 单位时间，即如果一条边上怪物的经验值为 (6)，你不能花费 (frac{1}{2}) 单位的时间得到 (3) 的经验值，而始终应该将一条边走完（哪怕只需要 (3) 的经验值）。

输入示例

2
6 147
0 1 0 50 0 0
0 0 1 0 0 0
20 0 0 0 0 0
0 0 0 0 1 50
0 0 0 8 0 0
0 0 0 0 0 3
6 152
0 1 0 50 0 0
0 0 1 0 0 0
20 0 0 0 0 0
0 0 0 0 1 50
0 0 0 8 0 0
0 0 0 0 0 3

输出示例

9
10

数据规模及约定

有如下几类具有特点的数据：

有 (10 exttt{%}) 的数据所有的 (n = 2)；
有 (20 exttt{%}) 的数据 (E le 3000)；
有 (20 exttt{%}) 的数据若 (S_{i, j} e 0)，则有 (S{i, j} ge 10^{15})；
有 (20 exttt{%}) 的数据所有的 (n = 40)。

以上各类数据互相之间均没有交集。对于所有数据 (1 le T le 6)，(n le 100)，(0 le S_{i, j} le E le 10^{18})。

数据保证至少存在一个环（包括自环），且至少存在一条点 (1) 通往这个环上某一点的路径。

题解

这是一个倍增 floyd。

令 (f(i, j, S)) 表示从节点 (i) 到节点 (j) 走恰好 (2^S) 步能得到的最大经验值。这个用一个类似 floyed 的 dp 就可以处理出来了。

然后对于答案，我们可以直接从高到底位枚举二进制。比如，先尝试 ((1000000)_2)，如果可以了就让第一位二进制变成 (0)，接着往下尝试（即下一次尝试 ((0100000)_2)）；否则下一步尝试 ((1100000)_2)。

怎么尝试呢？我们记一个数组 (g_i) 表示从 (1) 号节点到 (i) 号节点，经过“当前步数”能得到的最大经验值。借助刚刚处理出的 (f) 数组可以实现每一位二进制填 (1) 或 (0)。

然而，这样求出来的 (g_i) 是步数恰好等于“当前步数”的最大经验值，而这个东西并不关于“当前步数”单调（想一想，为什么），怎么解决？我们给每个点多连一个经验值为 (0) 的自环就好了（想一想，为什么）。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (s); i >= (t); i--)
#define LL long long

LL read() {
	LL x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

#define maxn 110
#define maxlog 61
#define ool (1ll << 60)

int n;
LL f[maxlog][maxn][maxn], lim, g[maxn], h[maxn];

int main() {
	freopen("train.in", "r", stdin);
	freopen("train.out", "w", stdout);
	
	int T = read();
	while(T--) {
		n = read(); lim = read();
		memset(f, -1, sizeof(f));
		rep(i, 1, n) rep(j, 1, n) {
			f[0][i][j] = read();
			if(!f[0][i][j]) f[0][i][j] = -1;
		}
		rep(i, 1, n) f[0][i][i] = max(f[0][i][i], 0ll);
		
		rep(s, 1, maxlog - 1) rep(i, 1, n) rep(j, 1, n) rep(k, 1, n) if(f[s-1][i][k] >= 0 && f[s-1][k][j] >= 0)
			f[s][i][j] = max(f[s][i][j], min(f[s-1][i][k] + f[s-1][k][j], lim));
//		rep(s, 1, maxlog - 1) rep(i, 1, n) rep(j, 1, n) if(f[s][i][j] >= 100) printf("f[%d][%d][%d] = %lld	", s, i, j, f[s][i][j]);
		LL tmp = 0, ans = ool;
		memset(g, -1, sizeof(g)); g[1] = 0;
		dwn(bit, maxlog - 1, 0) {
			tmp |= 1ll << bit;
			memset(h, -1, sizeof(h));
			bool ok = 0;
			rep(i, 1, n) {
				rep(k, 1, n) if(g[k] >= 0 && f[bit][k][i] >= 0) h[i] = max(h[i], min(g[k] + f[bit][k][i], lim));
				if(h[i] >= lim) ok = 1;
			}
			if(ok) ans = min(ans, tmp), tmp ^= 1ll << bit;
			else memcpy(g, h, sizeof(h));
		}
		
		printf("%lld
", ans);
	}
	
	return 0;
}