POJ2942Knights of the round table

这题第一次做的人一般是颓题解的。

首先我们转化一下问题，既然厌恶的人不能一起出席，是一种不传递关系，我们构建补图，这样补图的边表示两个骑士可以同时出席。

此时，由于只能有奇数个人参加，则我们要找出奇环，奇环内的人是可以同时参加的，而链上的是不可以的（想想为什么），而且根据题意，这样建图后的孤岛点是废的。所以缩vDcc（点双）的时候不用管他。为什么要缩点双呢？因为vDcc有这样一个性质：

只要一个vDcc中存在奇环，那么整个vDcc中的任意一点都至少在一个奇环中。

那么这样我们只要求出所有vDcc然后对每个vDcc跑染色法判定二分图就行了。这是因为一张无向图中有奇环，则它不是二分图，反之则有一张无向图是二分图则它不含奇环，这应该是一个充要条件。

所以总结一下流程：先建补图，然后tarjan求出所有vDcc，然后判断这个点双是否为二分图，若不是二分图，则这个vDcc里所有节点都可以参加。

上述流程的原因在上方有一些解释及定理。先给出实现，然后下方有些证明和染色法的微型解释。

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<cstdio>

#include<vector>

#include<queue>

#include<stack>

#include<set>

#include<map>

//#define db(x) cerr<<x<<"bug"<<endl

using namespace std;

struct EDGE{

    int ed,nex;

}edge[];int num,first[];

int root,n,m,time_,top,vccnum,ans;

int dfn[],low[],sta[],bl[],col[];

vector<int>vcc[];

bool can[],a[][];

int read(){

    int sum=,f=;char x=getchar();

    while(x<''||x>''){

        if(x=='-') f=-;

        x=getchar();

    }while(x>=''&&x<=''){

        sum=sum*+x-'';

        x=getchar();

    }return sum*f;

}

void init(){

    memset(first,,sizeof(first));

    num=time_=top=vccnum=ans=;

    memset(low,,sizeof(low));

    memset(dfn,,sizeof(dfn));

    memset(bl,,sizeof(bl));

    for(int i=;i<=n;i++) vcc[i].clear();

    memset(can,,sizeof(can));

    memset(col,,sizeof(col));

    memset(a,,sizeof(a));

}

void add(int st,int ed){

    edge[++num].ed=ed;

    edge[num].nex=first[st];

    first[st]=num;

}

bool bfs(int st,const int bln){

    queue<int>q;

    col[st]=;

    q.push(st);

    while(!q.empty()){

        int x=q.front();q.pop();

        for(int i=first[x];i;i=edge[i].nex){

            int y=edge[i].ed;

            if(bl[y]!=bln) continue;

            if(col[y]==col[x]) return ;

            else if(col[y]==-){

                col[y]=-col[x];

                q.push(y);

            }

        }

    }return ;

}

void tarjan(int x){

    dfn[x]=low[x]=++time_;

    sta[++top]=x;

    for(int i=first[x];i;i=edge[i].nex){

        int y=edge[i].ed;

        if(!dfn[y]){

            tarjan(y);

            low[x]=min(low[x],low[y]);

            if(low[y]>=dfn[x]){

                vcc[++vccnum].push_back(x);

                int p;

                do{

                    p=sta[top--];

                    vcc[vccnum].push_back(p);

                }while(p!=y);

            }

        }else low[x]=min(low[x],dfn[y]);

    }

}

int main(){

    while(){

        n=read();m=read();

        if(n==&&m==) return ;

        init();

        for(int i=,x,y;i<=m;i++){

            x=read();y=read();

            a[x][y]=a[y][x]=;

        }

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++){

                if(i==j) continue;

                if(a[i][j]) continue;

                add(i,j);

            }

    //    db(1);

        for(int i=;i<=n;i++)

            if(!dfn[i]) tarjan(i);

    //    db(2);

        for(int i=;i<=vccnum;i++){

            for(int j=;j<vcc[i].size();j++)

                bl[vcc[i][j]]=i,col[vcc[i][j]]=-;

            if(bfs(vcc[i][],i))

                for(int j=;j<vcc[i].size();j++)

                    can[vcc[i][j]]=;

        }

    //    db(3);

        for(int i=;i<=n;i++)

            if(!can[i]) ans++;

        printf("%d\n",ans);

    //    db(4);

    }return ;

}

证明：只要一个vDcc中存在奇环，那么整个vDcc中的任意一点都至少在一个奇环中。

首先，根据点双的含义，由于不存在割点，当存在一个奇环时，则任意一个点都可以有两条路径到达这个奇环上的两个点，从而将奇环分成两半，一半含奇数个点，另一半则含偶数个点。

而上述任意一点肯定跟着一条链（或者它自己连出两条边）接到这个环上（因为不这样会违背点双特性），当这个链上有偶数个节点时，可以和含奇数个点的半环构成奇环，若这个链上含有偶数个点，则可以和含奇数个点的半环构成奇环。

所以，该点一定位于奇环上。

那么，对所有点用同样的方式证明，可以得出上述结论。

证毕。

原谅这张丑陋的图。

证明：一张无向图中有奇环，则它不是二分图，反之则有一张无向图是二分图则它不含奇环。

首先，当一张图是二分（部）图时，它的两部内部一定不连边，只有两部之间的边，若成奇环的话，我们假定这个环上的节点为顺次的x₁,x₂,x₃,……x_2k-1，不妨设x₁位于左部，则x₂位于右部，x₃位于左部……x_2k-1位于左部，然后与x₁连边，不符合二分图的定义，所以一张二分图不含奇环。

同理，若图里含奇环，则无法构造出二分图，因为最终总会有一个点不能归属于任意一部。

证毕。

剩下的染色法又称黑白染色法。根据上述的二分图与奇环关系定理，我们尝试用黑白两种颜色标记图中的节点，当一个节点被染色后，与它相邻的节点则标记为相反颜色，若标记过程存在冲突，则说明奇环存在，这个可以自己画图去感受一下。

巴特西

POJ2942Knights of the round table

最新文章

热门文章