BZOJ-2208: [Jsoi2010]连通数

Description

给一张有向图，n<=2000，求每个点可及节点的个数和。

floyd传递闭包。需要用bitset优化。据说常数小32倍。。。
bitset的函数：

#include <bitset>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    //构造函数
    //string类型初始化
    string st("10010"); 
    bitset<10> bit1(st); cout<<bit1<<endl;
    //unsigned long 初始化 //长度不等时丢弃或者补0
    bitset<32> bit2(5); cout<<bit2<<endl;
    printf("%lu\n",bit2.to_ulong());//转化成unsigned long int

    //操作函数
    bitset<32>init; //0~31
    cout<<"initial: "<<init<<endl;//初始值为0
    init.set();//全变成1 
    cout<<"set():   "<<init<<endl;
    init.reset();//全变成0
    cout<<"reset(): "<<init<<endl;

    bitset<32>bi(0x3f3f3f3f);
    cout<<"bi:      "<<bi<<endl;
    printf("any(): %d\n",bi.any());//输出是否有1
    printf("size(): %d\n",bi.size());//输出二进制位的个数
    printf("count(): %d\n",bi.count()); //输出1的个数
    bi.flip(); //取反
    cout<<"flip(): "<<bi<<endl;
    int pos=5; cout<<"test(5): "<<bi.test(pos)<<endl; //在pos+1位是否为1
    return 0;
}

2208:

#include <bitset>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 2010
int n,ans;
bitset<N>map[N];
char st[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",st+1);
        for(int j=1;j<=n;++j)
            map[i][j]=(st[j]=='1');
        map[i][i]=1;
    }
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            if(map[i][k]) map[i]|=map[k];
    for(int i=1;i<=n;++i) ans+=map[i].count();
    printf("%d",ans);
    return 0;
}