首页 > 代码库 > BZOJ 2165 大楼 倍增Floyd
BZOJ 2165 大楼 倍增Floyd
题目大意:给定一张图,求从1开始到达m的权值至少需要遍历多少条边
n<=100,果断倍增Floyd
f[temp][i][j]表示经过2^temp条边从i走到j的最大权值
更新时f[temp[i][j]=max{f[temp-1][i][k]+f[temp-1][k][j]}
然后用矩阵g[i][j]记录当前走的权值,初始主对角线为0,其余为-∞
从大到小枚举temp,利用f[temp]和g得到矩阵h
如果h中1到某个点的权值超过了m就跳出 否则将当前temp计入ans 然后将g数组更新为h
最后输出ans+1就是答案 证明略
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n; long long f[70][110][110],g[110][110],h[110][110],m,ans; void Initialize() { ans=0; memset(f,0xef,sizeof f); memset(g,0xef,sizeof g); } int main() { int T,i,j,k,temp; for(cin>>T;T;T--) { Initialize(); cin>>n>>m; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { #ifndef ONLINE_JUDGE scanf("%I64d",&f[0][i][j]); #else scanf("%lld",&f[0][i][j]); #endif if(!f[0][i][j]) f[0][i][j]=0xefefefefefefefefll; } try{ for(temp=1;1ll<<temp<=m;temp++) for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) { f[temp][i][j]=max(f[temp][i][j],f[temp-1][i][k]+f[temp-1][k][j]); if(i==1&&f[temp][i][j]>=m) throw(true); } } catch(bool) {} for(i=1;i<=n;i++) g[i][i]=0; while(temp--) { memset(h,0xef,sizeof h); try{ for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) { h[i][j]=max(h[i][j],f[temp][i][k]+g[k][j]); if(i==1&&h[i][j]>=m) throw(true); } memcpy(g,h,sizeof g);ans+=1ll<<temp; } catch(bool) {} } cout<<ans+1<<endl; } return 0; } //lld!!!!
BZOJ 2165 大楼 倍增Floyd
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。