floyd优化题目 bzoj2208

BZOJ2208

JSOI2010

蒟蒻来一发 滋滋

题目

联通数 一道好像不很难的题

用了bitset 上代码吧

    #include<cstdio>
    #include<bitset>
    #include<iostream>
    using namespace std;
    int main(){
      int n;
      int x;
      int ans=0;
      bitset<2050> di[2050];
      scanf("%d",&n);
      for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        scanf("%1d",&x);
        di[i][j]=x;
        }
        di[i][i]=1;
      }
        for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
          if(di[i][k])
            di[i]|=di[k];
        for(int i=1;i<=n;i++)
        {
          ans+=di[i].count();
        }    
        printf("%d\n",ans);
        return 0;
    }

一个Floyd的优化

O（n^3/32）

时间复杂度约为O（n^3/32） 如果用int型储存则常数为32，如果用lang lang则常数为64 因为bitset是按位储存啊

优化过程是通过位运算进行异或操作 请注意floyd内循环的改变

大概就这样——

很短