首页 > 代码库 > hdu5036 Explosion 传递闭包
hdu5036 Explosion 传递闭包
大哲哥的讲课内容
根据期望的线性性,得到总期望为各个点被轰的概率(不会证,好像是这样吧)
传递闭包解决出每个点的祖先(能到达它的点)就能算概率了
bitset能贡献1/w的复杂度,而且导致Floyd只剩下两个for了(一点都不像经典Floyd)
1 #include <bits/stdc++.h> 2 using namespace std; 3 int T,n,m,t; 4 bitset<1001> a[1001]; 5 int main() 6 { 7 scanf("%d",&T); 8 for(int cas=1;cas<=T;cas++) 9 { 10 scanf("%d",&n); 11 for(int i=1;i<=n;i++) 12 a[i].reset(),a[i][i]=1; 13 for(int i=1;i<=n;i++) 14 { 15 scanf("%d",&m); 16 for(int j=1;j<=m;j++) 17 scanf("%d",&t),a[t][i]=1; 18 } 19 for(int i=1;i<=n;i++) 20 for(int j=1;j<=n;j++) 21 if(a[j][i]) 22 a[j]|=a[i]; 23 double ans=0; 24 for(int i=1;i<=n;i++) 25 ans+=1.0/a[i].count(); 26 printf("Case #%d: %.5f\n",cas,ans); 27 } 28 return 0; 29 }
hdu5036 Explosion 传递闭包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。