題目鏈接
題意看這吧。。https://www.cnblogs.com/wenruo/p/5885948.html
\(Solution\)
每對夫婦只能有一個坐在新娘這一邊，這正符合2-SAT初始狀態
若以0表示新娘，以1表示新郎
那么對于有關系的u,v(i'表示在新娘一側)，應該連邊u->v',v->u'，而不是用i'表示新娘對面(新郎一側)，而連邊u'->v,v'->u
因為如果新郎與v有關系，就會連邊1(u')->v'，這成了同在新郎一側了；但若新娘與v有關系，連邊0(u)->v'(同在新娘一側)是符合連邊規則的
有矛盾的情況是有關系的兩人同在新娘對面，所以2-SAT求出的可行解是新娘對面的
新娘與新郎要坐在兩側，連邊0->1，表示不能選0，一定選1，這樣選出來的解就是新娘對面了
每對夫婦就是對立的，也不分性別。。所以隨便一個表示i，另一個就表示i'
輸出方案時只要輸出與新娘染色相同的就可以了
是bel[i]還是i不要混 注意與新郎新娘標號統一
總是有點想不明白。。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
const int N=5005,M=1e5+5;int n,m,Enum,H[N],nxt[M],to[M],sk[N],top,cnt,bel[N],low[N],dfn[N],id;
int num,head[N],snxt[N],sto[N],conf[N],dgr[N]/*indgree*/,col[N],q[N];//conflict
bool ins[N];inline int read()
{int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now;
}
inline void AddEdge(int u,int v){to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
}
inline void AddEdge2(int u,int v){++dgr[v], sto[++num]=v, snxt[num]=head[u], head[u]=num;
}
void Tarjan(int x)
{dfn[x]=low[x]=++id, sk[++top]=x, ins[x]=1;for(int v,i=H[x]; i; i=nxt[i])if(!dfn[v=to[i]]) Tarjan(v), low[x]=std::min(low[x],low[v]);else if(ins[v]) low[x]=std::min(low[x],dfn[v]);if(low[x]==dfn[x]){++cnt;do{bel[sk[top]]=cnt, ins[sk[top--]]=0;}while(x!=sk[top+1]);}
}
bool Topo()
{for(int i=0; i<n<<1; i+=2)if(bel[i]==bel[i^1]) return 0;else conf[bel[i]]=bel[i^1],conf[bel[i^1]]=bel[i];num=0, memset(head,0,sizeof head),memset(col,0,sizeof col), memset(dgr,0,sizeof dgr);for(int x=0; x<n<<1; ++x)for(int i=H[x]; i; i=nxt[i])if(bel[x]!=bel[to[i]]) AddEdge2(bel[to[i]],bel[x]);int h=0,t=0;for(int i=1; i<=cnt; ++i)if(!dgr[i]) q[t++]=i;while(h<t){int x=q[h++];if(!col[x]) col[x]=1,col[conf[x]]=2;for(int i=head[x]; i; i=snxt[i])if(!--dgr[sto[i]]) q[t++]=sto[i];}return 1;
}int main()
{while(n=read(),m=read(),n&&m){id=top=cnt=Enum=0, memset(H,0,sizeof H);memset(dfn,0,sizeof dfn);char c,d; int a,b,s,t;while(m--){scanf("%d%c %d%c",&a,&c,&b,&d);
// s= c=='h'?a<<1:a<<1|1;//WA：這表示的man是2a，但是新郎也是man 是2a+1=1 s= c=='w'?a<<1:a<<1|1;t= d=='w'?b<<1:b<<1|1;AddEdge(s,t^1), AddEdge(t,s^1);}AddEdge(0,1);for(int i=0; i<n<<1; ++i)if(!dfn[i]) Tarjan(i);if(Topo()){for(int i=1; i<n; ++i)if(col[bel[i<<1]]==1) printf("%dh ",i);else printf("%dw ",i);putchar('\n');}else puts("bad luck");}return 0;
}
轉載于:https://www.cnblogs.com/SovietPower/p/8487085.html
總結
以上是生活随笔為你收集整理的POJ.3648.Wedding(2-SAT)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
