Poj 3648 Wedding (2-sat 输出方案)

系统管理员 2022-08-11 16:51 28阅读 0赞

题意：有一对新人结婚，邀请n对夫妇去参加婚礼。有一张很长的桌子，人只能坐在桌子的两边，还要满足下面的要求：1.每对夫妇不能坐在同一侧 2.n对夫妇之中可能有通奸关系（包括男男，男女，女女），有通奸关系的不能同时坐在新娘的对面，可以分开坐，可以同时坐在新娘这一侧。如果存在一种可行的方案，输出与新娘同侧的人。

思路：求解的时候去选择和新郎同一侧的人，输出的时候换一下就是新娘同一侧的人。

以上摘自kuangbin 大神的blog

#include <cstdio>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    using namespace std;
    #define WHITE -1  
    #define RED 1  
    #define BLUE 0
    
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int MAXN = 105;  
    const int VN   = MAXN*2;  
    const int EN   = VN*VN*2; 
    int n,m;
    
    struct Edge{
    	int u,v,next;
    };
    
    class Graph{
    public:
    	int head[VN],size;
    	Edge E[EN];
    	void init(){
    		size = 0;
    		memset(head, -1, sizeof(head));
    	}
    	void Add (int u,int v){
    		E[size].u = u;
    		E[size].v = v;
    		E[size].next = head[u];
    		head[u] = size++;
    	}
    }g,g1; //g为原图,g2为新图
    
    class Two_Sat{
    public:
    	bool Check (const Graph&g, const int n){
    		SCC(g,n);
    		for (int i=0;i<n;i++)
    			if (belong[i*2] == belong[i*2+1])
    				return false;
    		return true;
    	}
    	
    	void toposort (const Graph&g, Graph& g1, const int n) {
    		g1.init();  
    		memset(indeg, 0, sizeof(indeg));
    		int i;
    		for (i=0;i<n;i++){
    			opp[belong[i*2]] = belong[i*2+1];
    			opp[belong[i*2+1]] = belong[i*2];
    		}
    		for (int e=0;e<g.size;e++){
    			int u = belong[g.E[e].u];
    			int v = belong[g.E[e].v];
    			if (u == v) continue;
    			indeg[u]++;
    			g1.Add(v,u);
    		}
    		
    		queue<int>que;  
    		memset(color, WHITE, sizeof(color));  
    		for (i=1;i<=bcnt;i++)
    			if (!indeg[i])
    				que.push(i);
    
    		int* head = g1.head;
    		Edge* E   = g1.E;
    		
    		while (!que.empty()){
    			int u = que.front();
    			que.pop();
    			if (color[u] != WHITE) continue;
    			color[u] = RED;
    			color[opp[u]] = BLUE;
    
    			for (int e=head[u]; e!=-1; e=E[e].next){
    				int v = E[e].v;
    				if (--indeg[v] == 0)
    					que.push(v);
    			}
    		}
    
    		// 输出方案  
    		printf("1%c",color[belong[2]]==RED?'w':'h');
    		for (i=2;i<n;i++)
    			printf(" %d%c",i,color[belong[i*2]]==RED?'w':'h');
    		printf("\n");
    	}
    
    private:
    	int top, bcnt, idx;
    	int sta[VN],belong[VN];
    	int dfn[VN],low[VN];
    	bool inStack[VN];
    
    	// 求方案  
    	int indeg[VN];
    	int color[VN];
    	int opp[VN];
    	
    	void targan (const Graph&g, const int u){
    		int v;
    		dfn[u] = low[u] = ++idx;
    		sta[top++] = u;
    		inStack[u] = true;
    		
    		for (int i=g.head[u]; i!=-1; i=g.E[i].next){
    			v = g.E[i].v;
    			if (dfn[v] < 0){
    				targan(g, v);
    				low[u] = min(low[u], low[v]);
    			}
    			else if(inStack[v])
    				low[u] = min(low[u], dfn[v]);
    		}
    		
    		if (dfn[u] == low[u]){
    			++bcnt;
    			do{
    				v = sta[--top];
    				inStack[v] = false;
    				belong[v] = bcnt;
    			}while(u != v);
    		}
    	}
    
    	void SCC (const Graph&g, int n){
    		top=bcnt=idx=0;
    		memset(dfn,-1,sizeof(dfn));
    		memset(low,0,sizeof(low));
    		memset(belong,0,sizeof(belong));
    		memset(inStack,false,sizeof(inStack));
    		for (int i=0; i<2*n;i++)
    			if (dfn[i] < 0) targan(g,i);
    	}
    }sat;
      
    int main ()
    {
    	char ch1,ch2;
    	while (scanf("%d%d",&n,&m) && n+m)
    	{
    		g.init();
    		g.Add(1,0);   //新郎必选,因为新郎也可能有JQ
    		for (int i=0;i<m;i++)
    		{
    			int a,b,u,v;
    			scanf("%d%c%d%c",&a,&ch1,&b,&ch2);
    			u=a*2,v=b*2;
    			if (ch1=='h' && ch2=='h')
    				g.Add(u,v^1),g.Add(v,u^1);
    			if (ch1=='h' && ch2=='w')
    				g.Add(u,v),g.Add(v^1,u^1);
    			if (ch1=='w' && ch2=='h')
    				g.Add(u^1,v^1),g.Add(v,u);
    			if (ch1=='w' && ch2=='w')
    				g.Add(u^1,v),g.Add(v^1,u);
    		}
    		if (sat.Check(g,n)==false)
    			puts("bad luck");
    		else
    			sat.toposort(g,g1,n);
    	}
    	return 0;
    }