PAT 习题bitset 06-图3 六度空间 （30 分）

#include<iostream>
#include<string>
#include<bitset>


using namespace std;
int N, M;

bool visited[1000];
bitset<1'000> *map;

double percent(const bitset<1000> &src, int n) {//求一个人的n度认识人的集合
    bitset<1000> totest(src);
    bitset<1000> next;
    bitset<1000> target(src);

    do {
        for (int i = 0; i < N; ++i) {
            if (totest.test(i)) {//如果某位不为0
                next |= map[i];            //next和map[i]相或,next就是根据xx你可以认识的人
            }
        }
        target |= next;//targe和next或
        totest ^= next;    //异或得到差集
        next.reset();//filp是翻转,~
        
        --n;
    } while (n != 0);

    return target.count() / (double)N;

}



int main() {
    //freopen("in.txt", "r", stdin);
    int  a, b;
    cin >> N >> M;
    
    //bitset<1'000> *map = new(0x0) bitset<1000>[1000];//初始值为0
    map = new bitset<1000>[1000];//初始值为0

    for (int i = 0; i < M; ++i) {
        cin >> a >> b;
        map[a-1][b-1] = 1;
        map[b-1].set(a-1);        //同上

    }//创建图

    for (int i = 0; i < N; ++i) {
        printf("%d: %.2lf%%\n", i+1, percent(map[i],5)*100);
    }


    return 0;
}

先上代码,我不会把每道题都上传解析,但是如果我觉得有不错的收益,或者认为写的够好,可能会考虑发上来记下,主要也是一个学习记忆的过程.

 

题目意思:　　求一个人根据6层关系能够认识的人占所有人的比例,一个有关图的求解问题.基本解题思路不难,主要是我这里创新了一把.STL中的bitset,位图集合,图的模型是位图矩阵.

思路:　　按位或可以求得并集,异或可以求得差集,与可以求得交集,取反可以求得补集.一个人能通过 六层关系认识的人  就是 5层以内认识的人(含自己)的朋友的并集.

按照这个思路,percent函数里,totest是一层新增朋友的的集合,注意是新增,为了确保新增,不需要进行不必要的循环或,24行代码求了一个差集,也就是说,如果我能在我已经认识乙了,就不再需要通过甲去认识乙.(这一步能省大量时间),其实也可以和target进行求差集,(更稳妥)

target储存所有朋友集合,每一次dowhile循环target就会求得一层朋友.

主要使用了bitset,操作集包括与,或,异或,[]被重载为返回某一位的引用,不过这个应该是返回的是封装了的对象,因为原生没有位,效率不如bitset.test(),set,reset,这样.

改变了上面一点,以及把cin改成scanf后,时间竟然达到了恐怖的38ms,而且只有60行不到的代码,就是不好想出来,我真牛批.....,

 

 

时间上面,虽然是邻接矩阵,但是因为量不大,且位操作快,主要也只是占用了额外空间,再就是按位与或没有区分长度.但是在这个量级速度远快于邻接链表等等.

 

 

翻了几页,连61ms都无人能够超越~