NPC问题：服务商+bitset用法

原题：

参考的是Program Challenge的CSDN解析

数据结构上的绝妙是利用bitset来压缩信息的存储.可以认为把二位vector中的行变为bitset，即每个单位由int变为bit，则每一行对应一个点的连通信息，每个比特对应点对点是否连通。之后的DFS中，通过位运算可以简洁的合并信息并进行判断。

set(i); //把bitset的第i位比特设置成1
test(i);//检查bitset的第i位是1则返回true
count();//数bitset中有多少位是1
对bitset可以做位运算

这是一个NPC问题，多项式时间内没有解法，但是可以多项式时间验证解是否正确。作为一个图论问题，自然想到用DFS或者BFS来做。为了求出最小的站点数，从小到大遍历答案并检查。

这里为了简化求解，把图拆封成连通分量分别求解，每个连通分量上的最小解的和就是整个图的最小解。在压入每一个点的信息（即每一行bitset）的时候，可以认为对子图进行了重新编号。

还有一处简化是是通过覆盖率来剪枝。由于遍历是按照序号从小到大来遍历的，back的意思是，从当前点往更大的点遍历，能有多少个点被服务站覆盖。因此填写信息的时候是从序号大的点往序号小的点遍历，因为较大序号的点不会再去遍历小序号的点。这里主要是为了剪枝以下情况。（左侧是结果树）

可以看到在对1的处理中，对5做DFS是没有意义的，因此剪枝。

由于本身建站和相邻建站都算覆盖，这里的连通实际上也代表了覆盖的情况。因此可以通过或运算来计算覆盖的情况。

以下是对原作者代码的注释

#include <iostream>
#include <vector>
#include <deque>
#include <bitset>

const int MAX_N=25;

using namespace std;

//划分出连通分量
void divideGraph(const vector<bitset<MAX_N>> &graph,vector<vector<bitset<MAX_N>>> &vecChildGraph)
{
    /*
    graph 原本的图，graph[i]代表序号为i的点所处的连通分量的记录图
    vecChildGraph 用于存储子图的vector
    */
    size_t N =graph.size();
    vector<size_t> vecVisited(N,false);
    //用于记录每一个点是否已经被遍历并归入一个连通子图
    for(size_t i=0;i<N;++i)
    {
        if(!vecVisited[i])//点还没遍历
        {
            vector<bitset<MAX_N>> ChildGraph;
            deque<size_t> que;//BFS找连通分量
            que.push_back(i);
            vecVisited[i]=true;
            size_t front;
            while(!que.empty())
            {
                front = que.front();
                que.pop_front();
                ChildGraph.push_back(graph[front]);//构建连通图信息中的行
                for(size_t pos=0;pos<N;pos++)
                {
                    if(graph[front].test(pos) && !vecVisited[pos])
                    {
                        que.push_back(pos);
                        vecVisited[pos]=true;
                    }
                }
            }
            vecChildGraph.push_back(ChildGraph);
        }
    }
}

void calBackCover(vector<vector<bitset<MAX_N>>> &vecChildGraph,vector<vector<bitset<MAX_N>>> &vecBackCover)
{
    //vecChildGraph是连通子图的集合，vecBackCover是记录覆盖率信息的二维bitset，每一行代表遍历到该行序列对应的点的覆盖率信息
    for(size_t idx=0;idx<vecChildGraph.size();idx++)
    {
        const vector<bitset<MAX_N>> &childGraph = vecChildGraph[idx];
        size_t node = childGraph.size();
        //取出一个子图 记录下子图中节点的数量
        vecBackCover.push_back(vector<bitset<MAX_N>>(node,bitset<MAX_N>()));
        //生成一个二维bitset对应该子图，并放入答案vector中
        bitset<MAX_N> BackCover;
        //中间变量 代表一个点的覆盖率信息
        for(;node>0;--node)
        {
            vecBackCover[idx][node-1]=childGraph[node-1]|BackCover;
            //直接对bitset进行或运算来得到连通信息 bitset默认初始值应该是全0
            BackCover=vecBackCover[idx][node-1];
            //记录下来 下一轮继续用 因为是层层向序号小的节点传递的连通的信息 小节点的信息依赖于序号更大的覆盖率的数据
        }
    }
}

void DFS(const vector<bitset<MAX_N>> &graph,const vector<bitset<MAX_N>> &back,bitset<MAX_N> &cover,size_t curr,size_t cnt,const size_t bound,size_t &num)
{
    /*
    graph 处理后的连通子图 确保只有一个连通分量
    back 该子图上每个点的覆盖率信息
    cover 遍历到当前点的已有的覆盖子图的情况
    curr 当前遍历的点的序号
    cnt 当前已经建立的服务站的数量
    bound 最多能建的服务站的数量
    num 最终返回的答案
    */
    if(cnt==bound)
    {
        if(cover.count()==graph.size())
            num=cnt;
       	return;
        //验证当前的bound是否能够使得点都被覆盖 如果是，确定答案并返回
    }
    bitset<MAX_N> newCover;
    for(size_t i=curr;i<graph.size();++i)
    {
        newCover = cover;
        newCover |=back[curr];
        if(newCover.count()!=graph.size())
            continue;
        //做覆盖率的剪枝 现有的覆盖情况与curr覆盖如果合起来不是全图 那么一直不会对之后的点做DFS
        newCover = cover;
        newCover |= graph[i];//更新情况
        if(newCover == cover)
            continue;
        //覆盖率没有变化 不需要遍历选中的i点 剪枝
        DFS(graph,back,newCover,i+1,cnt+1,bound,num);
        //对i建站并更新 记录新的覆盖情况，从下一个点开始遍历
        if(num!=0)
            break;
       	//已经有答案 不用再继续
    }
}

int main()
{
    size_t N=0,M=0;
    while(cin>>N>>M)
    {
        if(N==0 && M==0)
            break;
        vector<bitset<MAX_N>> graph(N,bitset<MAX_N>());
        for(size_t v=0;v<N;++v)
        {
            graph[v].set(v);
            //自己与自己算连通
        }
        size_t v1,v2;
        for(size_t m=0;m<M;++m)
        {
            cin>>v1>>v2;
            graph[v1-1].set(v2-1);
            graph[v2-1].set(v1-1);
            //记录路径信息 注意下标已经双向
        }
        vector<vector<bitset<MAX_N>>> vecChildGraph;
        vector<vector<bitset<MAX_N>>> vecBackCover;
        divideGraph(graph,vecChildGraph);//划分连通子图
        calBackCover(vecChildGraph,vecBackCover);//求每个子图中每个点的覆盖率
        size_t total=0;
        for(size_t idx=0;idx<vecChildGraph.size();++idx)
        {
            const vector<bitset<MAX_N>> &childGraph = vecChildGraph[idx];
            const vector<bitset<MAX_N>>& back=vecBackCover[idx];
            bitset<MAX_N> cover;
            size_t num=0;
            for(size_t bound=1;bound<=childGraph.size();++bound)
            {
                DFS(childGraph,back,cover,0,0,bound,num);//对每个bound做验证 NPC问题
                if(num!=0)
                    break;//有解
            }
            total+=num;
        }
        cout<<total<<endl;
    }
    return 0;
}