poj 3648 2-sat 输出任意一组解模板

转载地址：http://blog.csdn.net/qq172108805/article/details/7603351

/*

2-sat问题,题意：有对情侣结婚，请来n-1对夫妇，算上他们自己共n对，编号为0~~n-1,他们自己编号为0

所有人坐在桌子两旁，新娘不想看到对面的人有夫妻关系或偷奸关系，若有解，输出一组解，无解输出bad luck

思路：

1.根据偷奸关系建图(1h和2h有偷奸关系，建边1h->2w    2h->1w)

2.求强连通分量

3.判断有无解(任一对夫妇不在同一强连通分量中，有解；否则无解)

4.缩点建图(建反向图)

5.拓扑排序

6.由底向上求解(由于上面建的是反向图，所以自顶(无入度)向下)

至此，选出来的是做新娘对面的，要求输出，坐在新娘一边的

*/

#include<stdio.h>

#include<string.h>

#include<queue>

#include<stack>

using namespace std;

struct edge

{

	int yong;

	int v[1000000];

	int next[1000000];

	int head[1000000];

	edge()

	{

		clear();

	}

	void clear()

	{

		yong=1;

		memset(head,0,sizeof(head));

	}

	void add(int u,int w)

	{

		v[yong]=w;

		next[yong]=head[u];

		head[u]=yong;

		yong++;

	}

}e1,e2;

int dfn[1000],low[1000];

int n,m,index,scc;

queue<int>q;

stack<int>ss;

int ins[1000],belong[1000],dui[1000],ind[1000],fang[1000];

void tarjan(int u)//tarjan求强连通分量

{

	int i,v;

	dfn[u]=low[u]=index++;

	ins[u]=1;

	ss.push(u);//之前误写成队列

	for(i=e1.head[u];i;i=e1.next[i])

	{

		v=e1.v[i];

		if(dfn[v]==0)

		{

			tarjan(v);

			if(low[v]<low[u])

				low[u]=low[v];

		}else if(ins[v]&&dfn[v]<low[u])

			low[u]=dfn[v];

	}

	if(low[u]==dfn[u])

	{

		do{

			v=ss.top();

			ss.pop();

			ins[v]=0;

			belong[v]=scc;//标记所属强连通分量的标号

		}while(v!=u);

		scc++;

	}

}

void topsort()//拓扑排序  和  求解

{

	int v,u;

	while(!q.empty())

		q.pop();

	int i;

	for(i=0;i<scc;i++)

	{

		if(ind[i]==0)//0入度的节点入队

			q.push(i);

	}

	while(!q.empty())

	{

		v=q.front();

		q.pop();

		if(!fang[v])//0入度的节点涂色

		{//fang[i]表示标号为i的强连通分量被选择  或  删除

			fang[v]=1;//表示选择

			fang[dui[v]]=2;//表示删除

		}

		for(i=e2.head[v];i;i=e2.next[i])

		{

			u=e2.v[i];

			if(--ind[u]==0)//减入度，0入度的入队

			{

				q.push(u);

			}

		}

	}

}

int main()

{

	int i,j,a,b,v;

	char c1,c2;

	while(scanf("%d%d",&n,&m),m+n)

	{//初始化

		e1.clear();

		e2.clear();

		//建原图

		for(i=1;i<=m;i++)

		{

			scanf("%d%c %d%c",&a,&c1,&b,&c2);

			e1.add(c1=='h'?a*2+1:a*2,c2=='h'?b*2:b*2+1);

			e1.add(c2=='h'?b*2+1:b*2,c1=='h'?a*2:a*2+1);//这里处理要仔细

		}

		e1.add(0,1);//新郎必选

		//求强连通分量

		index=1;//dfn[]标记

		scc=0;//强连通分量个数，从0开始计数

		memset(dfn,0,sizeof(dfn));

		memset(ins,0,sizeof(ins));

		for(i=0;i<2*n;i++)

		{

			if(!dfn[i])

				tarjan(i);

		}

		//判断有无解

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

		{//belong[i]表示i所属的强连通分量的标号

			if(belong[2*i]==belong[2*i+1])//若有夫妇在同一强连通分量中，无解

				break;

			dui[belong[2*i+1]]=belong[2*i];//记录配偶所属的强连通分量的标号，求解的时候有用

			dui[belong[2*i]]=belong[2*i+1];

		}

		if(i!=n)

		{

			printf("bad luck\n");

			continue;

		}

		//构建反向缩点图

		memset(ind,0,sizeof(ind));

		for(i=0;i<2*n;i++)

		{

			for(j=e1.head[i];j;j=e1.next[j])

			{

				v=e1.v[j];

				if(belong[i]!=belong[v])

				{

					e2.add(belong[v],belong[i]);//注意，这里的顺序

					ind[belong[i]]++;//统计入度

				}

			}

		}

		//拓扑排序  和  求解  同时进行了

		memset(fang,0,sizeof(fang));

		topsort();

		//输出解

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

		{

			if(fang[belong[2*i]]==1)

				printf("%dh ",i);

			else printf("%dw ",i);

		}

		printf("\n");

	}

	return 0;

}

巴特西

poj 3648 2-sat 输出任意一组解模板

最新文章

热门文章