程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 2165 大樓 倍增Floyd

BZOJ 2165 大樓 倍增Floyd

編輯:C++入門知識

BZOJ 2165 大樓 倍增Floyd


題目大意:給出一個有向圖,問總路徑長度>=k最少需要經過多少邊。


思路:記錄幾個輔助數組,f[p][i][j]表示走2^p步時最長的路徑是多少。g[i][j]表示目前從i到j最長路是多長。

f的dp方程是f[p][i][j] = max(f[p][i][j],f[i - 1][i][j] = f[i - 1][j][k]);

然後在處理g數組的時候當從1開始的最長路大於等於k的時候就直接break掉,這個時候不計入總答案,否則計入總答案。

這樣就處理出了總長度


CODE:

#include 
#include 
#include 
#include 
#define MAX 110
using 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;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved