題目大意：給出一個(gè)有向圖，問總路徑長(zhǎng)度>=k最少需要經(jīng)過多少邊，
BZOJ 2165 大樓 倍增Floyd
。思路：記錄幾個(gè)輔助數(shù)組，f[p][i][j]表示走2^p步時(shí)最長(zhǎng)的路徑是多少。g[i][j]表示目前從i到j(luò)最長(zhǎng)路是多長(zhǎng)。
f的dp方程是f[p][i][j] = max(f[p][i][j],f[i - 1][i][j] = f[i - 1][j][k]);
然后在處理g數(shù)組的時(shí)候當(dāng)從1開始的最長(zhǎng)路大于等于k的時(shí)候就直接break掉，這個(gè)時(shí)候不計(jì)入總答案，否則計(jì)入總答案。
這樣就處理出了總長(zhǎng)度 CODE： #include<cstdio>#include<cstring>#include<iostream>#include #define MAX 110using namespace std; int T,points;long long f[70][MAX][MAX],g[MAX][MAX],t[MAX][MAX],len,ans; inline void Initialize(){ ans = 0; memset(f,0xef,sizeof(f)); memset(g,0xef,sizeof(g)); for(int i = 1; i<= points; ++i) g[i][i] = 0;} int main(){ for(cin >>T; T--;) { scanf("%d%lld",&points,&len); Initialize(); for(int i = 1; i<= points; ++i) for(int j = 1; j<= points; ++j) { scanf("%lld",&f[0][i][j]); if(!f[0][i][j]) f[0][i][j] = 0xefefefefefefefefll; } int p = 1; try{ for(; 1ll<< p<= len; ++p) for(int k = 1; k<= points; ++k) for(int i = 1; i<= points; ++i) for(int j = 1; j<= points; ++j) { f[p][i][j] = max(f[p][i][j],f[p - 1][i][k] + f[p - 1][k][j]); if(i == 1 && f[p][i][j] >= len) throw(true); } } catch(bool) {} while(p--) { memset(t,0xef,sizeof(t)); try{ for(int k = 1; k<= points; ++k) for(int i = 1; i<= points; ++i) for(int j = 1; j<= points; ++j) { t[i][j] = max(t[i][j],f[p][i][k] + g[k][j]); if(i == 1 && t[i][j] >= len) throw(true); } memcpy(g,t,sizeof(g)); ans += 1ll<< p; } catch(bool) {} } printf("%lld\n",ans + 1); } return 0;}