bzoj2165 -- 倍增floyd
2018-06-17 22:39:24来源:未知 阅读 ()
题意:给定一张有向图,求图中从1开始长度>=m且边数最少的路径经过的边数。
考虑倍增floyd。
令f[p][i][j]表示经过2p条边从i到j的最大长度。
那么f[p][i][j]=max{f[p-1][i][k]+f[p-1][k][j]}
令g[i][j]表示当前答案从i到j的最大长度。
求答案时从大到小枚举每个二进制位,更新g,若不存在从1开始长度>=m的路径,这一位就是1。
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define INF (1ll<<62) 7 #define N 110 8 #define M 70 9 #define ll long long 10 ll m,f[M][N][N],A[N][N],t[N][N],Ans; 11 int i,j,k,n,p,T; 12 inline ll Max(ll x,ll y){return x<y?y:x;} 13 inline void Init(){ 14 memset(f,0xef,sizeof(f)); 15 memset(A,0xef,sizeof(A)); 16 Ans=0; 17 } 18 int main(){ 19 scanf("%d",&T); 20 while(T--){ 21 scanf("%d%lld",&n,&m); 22 Init(); 23 for(i=1;i<=n;i++) 24 for(j=1;j<=n;j++){ 25 scanf("%lld",&f[0][i][j]); 26 if(f[0][i][j]==0)f[0][i][j]=-INF; 27 } 28 for(p=1;1ll<<p<=m;p++){ 29 for(k=1;k<=n;k++){ 30 for(i=1;i<=n;i++){ 31 for(j=1;j<=n;j++){ 32 f[p][i][j]=Max(f[p][i][j],f[p-1][i][k]+f[p-1][k][j]); 33 if(i==1&&f[p][i][j]>=m)break; 34 } 35 if(j<=n)break; 36 } 37 if(i<=n)break; 38 } 39 if(k<=n)break; 40 } 41 for(i=1;i<=n;i++)A[i][i]=0; 42 while(p--){ 43 memset(t,0xef,sizeof(t)); 44 for(k=1;k<=n;k++){ 45 for(i=1;i<=n;i++){ 46 for(j=1;j<=n;j++){ 47 t[i][j]=Max(t[i][j],f[p][i][k]+A[k][j]); 48 if(i==1&&t[i][j]>=m)break; 49 } 50 if(j<=n)break; 51 } 52 if(i<=n)break; 53 } 54 if(k>n){ 55 memcpy(A,t,sizeof(A)); 56 Ans+=1ll<<p; 57 } 58 } 59 printf("%lld\n",Ans+1); 60 } 61 return 0; 62 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 倍增法求LCA(最近公共最先) 2019-04-25
- BZOJ1491: [NOI2007]社交网络(Floyd 最短路计数) 2018-07-06
- Floyd 算法详解 2018-06-29
- 2016弱校联盟十一专场10.5---As Easy As Possible(倍增) 2018-06-17
- 后缀数组的倍增算法(Prefix Doubling) 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash