旅游网站开发公司,建设部网站官网 取消八大员,佛山快速排名优化,微商城开发费用多少题目链接#xff1a;
题目 建图#xff1a;
1.新娘向新郎连边#xff0c;表示选取的时候选取新娘对面的。
2.
有奸情的人比如是 xh yh那么连边(x,yn)以及(y,xn)
如果是xh yw 那么连边(x,y) 以及 (yn,x)
如果是xw yh 那么连边(xn,yn)以及(y,x)
如果是xw yw那么连边(x…题目链接
题目 建图
1.新娘向新郎连边表示选取的时候选取新娘对面的。
2.
有奸情的人比如是 xh yh那么连边(x,yn)以及(y,xn)
如果是xh yw 那么连边(x,y) 以及 (yn,x)
如果是xw yh 那么连边(xn,yn)以及(y,x)
如果是xw yw那么连边(xn,y)以及(y,xn)
其中 (x表示丈夫 x n xn表示妻子)
3.跑2-sat输出的时候注意输出新娘一边的。
因为我们选取的时候是按照新郎一边的选择的所以说输出的时候要取反再输出。
代码 #include vector
#include cstring
#include cstdio
#include queue
using namespace std;
const int maxn 1000;
int head[maxn];
int DFN[maxn],LOW[maxn],stk[maxn],visit[maxn],belong[maxn];
vectorint scc[maxn];
int tot,idx,cnt,sccnum;
int n,color[maxn],degree[maxn],pos[maxn];
struct Es{ int v; int next; int cost;
}Es[maxn1];
vectorint bkG[maxn];
void init(){ sccnum tot idx cnt 0; memset(head,-1,sizeof(head)); memset(DFN,0,sizeof(DFN)); memset(LOW,0,sizeof(LOW)); memset(visit,0,sizeof(visit)); memset(color,0,sizeof(color)); memset(degree,0,sizeof(degree));memset(pos,0,sizeof(pos));for(int i 0;i maxn;i) scc[i].clear();for(int i 0;i maxn;i) bkG[i].clear();
}
inline void add_edge(int i,int j,int cost 1){ Es[cnt].v j; Es[cnt].cost cost; Es[cnt].next head[i]; head[i] cnt;
}
void tarjan(int x)
{DFN[x]LOW[x]tot;stk[idx]x;visit[x]1;for(int ihead[x];i!-1;iEs[i].next){if(!DFN[Es[i].v]) {tarjan(Es[i].v);LOW[x] min(LOW[x],LOW[Es[i].v]);}else if(visit[Es[i].v ]){ LOW[x] min(LOW[x],DFN[Es[i].v]);}}if(LOW[x]DFN[x]){sccnum;do{int item stk[idx];belong[item] sccnum;scc[sccnum].push_back(item);visit[item]0;idx--;}while(x!stk[idx1]);}return ;
}
bool check(){for(int i 1;i n;i){if(belong[i] belong[in]) return false;}return true;
}
bool solve(){for(int i 1;i 2*n;i )if(!DFN[i]) tarjan(i);if(!check()) return false;for(int i 1;i n;i){if(!pos[belong[i]]){pos[belong[i]] belong[in];pos[belong[in]] belong[i];}}for(int i 1;i 2*n;i){for(int e head[i];e ! -1;e Es[e].next){int v Es[e].v;if(belong[i] ! belong[v]){degree[belong[i]];bkG[belong[v]].push_back(belong[i]);}}}queueint que;for(int i 1;i sccnum;i){if(!degree[i])que.push(i);}while(!que.empty()){int u que.front();que.pop();if(!color[u]){color[u] 1;color[pos[u]] 2;}for(int i 0;i bkG[u].size();i){int v bkG[u][i];degree[v]--;if(!degree[v])que.push(v);}}//在这里准备输出答案//为1表示选中为2表示为选中/*for(int i 1;i n;i){if(color[belong[i]] 1) {//Yes}else{//No}} */return true;
}
int main(){int m;while(~scanf(%d%d,n,m) n m){init();//n--;for(int i 0;i m;i){int a 0,b 0;char ta,tb;scanf(%d%c%d%c,a,ta,b,tb);a;b;add_edge(ta h?a:an,tb h?bn:b);add_edge(tb h?b:bn,ta h?an:a);}add_edge(n1,1);if(solve()){for(int i 2;i n;i){if(color[belong[i]] 1){printf(%d%c ,i-1,w);}else{printf(%d%c ,i-1,h);}}puts();}else{puts(bad luck);}}}
/*
3 2
1w 2w
1w 2h*/
