[BZOJ 2165] 大樓 【DP + 倍增 + 二進制】

題目鏈接：BZOJ - 2165

?

題目分析：

　　這道題我讀了題之后就想不出來怎么做，題解也找不到，于是就請教了黃學長，黃學長立刻秒掉了這道題，然后我再看他的題解才寫出來。。Orz

　　使用 DP + 倍增 ，用狀態 f[x][i][j] 表示從 i 出發，坐 x 次電梯到達 j ，最多能上升的層數。開始讀入的就是 f[1][][] 數組。（注意：若開始時 i 不能走到 j ， 則 f[1][i][j] = -INF）

　　使用倍增，用 f[x][][] 求出 f[x << 1][][] ， 一直求f[2^p][][], 直到出現求出的 f[][][] 數組第一行存在大于等于 m 的數值。

　　用 f[a][][] 和 f[b][][] 求出 f[a+b][][] 的狀態轉移方程是類似 Floyd 的 : f[a+b][i][j] = max(f[a][i][k] + f[b][k][j])?

　　之后枚舉每一個二進制位，拼湊答案。如果加入這個二進制位后仍不能達到 m ，就加入這一位。最后答案要加1。（類似倍增求LCA）

?　 寫代碼過程中出現的錯誤:最后拼湊答案的時候用的初始矩陣不應該是全0的，因為比如從 2->3 沒有邊，但這樣就增加了從 2->3 的長度為 0 的邊。所以應該是對角線為 0 ，其余為 -INF。（Orz Hzwer 找出了錯誤的原因）

代碼如下：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>using namespace std;const int MaxN = 100 + 5;typedef long long LL;const LL INF = 1e18;int T, n, Top;LL m, Ans;struct Matrix 
{LL Num[MaxN][MaxN];void Clear(LL x) {for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {Num[i][j] = x;}}}
} M[70 + 5], M0, Temp;LL gmax(LL a, LL b) {return a > b ? a : b;
}Matrix Mul(Matrix A, Matrix B) {Matrix ret;ret.Clear(-INF);for (int k = 1; k <= n; ++k) {for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {ret.Num[i][j] = gmax(ret.Num[i][j], A.Num[i][k] + B.Num[k][j]);if (ret.Num[i][j] > m) ret.Num[i][j] = m;}}}return ret;
}bool Check(Matrix A) {for (int i = 1; i <= n; ++i) if (A.Num[1][i] >= m) return true;return false;
}int main() 
{scanf("%d", &T);for (int Case = 1; Case <= T; ++Case) {scanf("%d%lld", &n, &m);for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {scanf("%lld", &M[0].Num[i][j]);if (M[0].Num[i][j] == 0ll) M[0].Num[i][j] = -INF;}}Top = 0;while (true) {++Top;M[Top] = Mul(M[Top - 1], M[Top - 1]);if (Check(M[Top])) break;}Ans = 0ll;M0.Clear(-INF);for (int i = 1; i <= n; ++i) M0.Num[i][i] = 0;for (int i = Top; i >= 0; --i) {Temp = Mul(M0, M[i]);if (!Check(Temp)) {M0 = Temp;Ans += (1ll << i);}}printf("%lld\n", Ans + 1);}return 0;
}