做租凭网站是经营性吗,跨境电商平台shopee,亚马逊一般在哪些网站上做推广,网站建设总体设计题目:
有n对夫妻被邀请参加一个聚会#xff0c;因为场地的问题#xff0c;每对夫妻中只有1人可以列席。在2n 个人中#xff0c;某些人之间有着很大的矛盾#xff08;当然夫妻之间是没有矛盾的#xff09;#xff0c;有矛盾的2个人是不会同时出现在聚会上的。有没有可能会…题目:
有n对夫妻被邀请参加一个聚会因为场地的问题每对夫妻中只有1人可以列席。在2n 个人中某些人之间有着很大的矛盾当然夫妻之间是没有矛盾的有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席
Input
n 表示有n对夫妻被邀请 (n 1000) m 表示有m 对矛盾关系 ( m (n - 1) * (n -1))
在接下来的m行中每行会有4个数字分别是 A1,A2,C1,C2 A1,A2分别表示是夫妻的编号 C1,C2 表示是妻子还是丈夫 0表示妻子 1是丈夫 夫妻编号从 0 到 n -1
Output
如果存在一种情况 则输出YES 否则输出 NO
Sample Input
2 1 0 1 1 1
Sample Output
YES
分析
2-sat详解:https://blog.csdn.net/zeng_jun_yv/article/details/105316871 一道2—SAT的模板题其实就是建立一个无向图然后求强连通分量再看看同一对夫妻是不是在同一个强连通分量里。由对称性解2-SAT问题
AC代码
/*由对称性解2-SAT问题*/
#include iostream
#include cstdio
#include cstring
#include vector
#include stack
#includealgorithm
using namespace std;
const int N 2010;
vectorint vec[N];
int n, m, id, cnt;
int dfn[N], vis[N], low[N], belong[N];
stackint s;
void init()
{memset(vis,0,sizeof(vis));memset(dfn,-1,sizeof(dfn));memset(low,-1,sizeof(low));memset(belong,-1,sizeof(belong));id cnt 0;while(!s.empty())s.pop();for(int i 0; i 2*n; i)vec[i].clear();
}
void tarjan(int u)
{dfn[u] low[u] id;vis[u] 1;int sz vec[u].size();s.push(u);for(int i 0; i sz; i){int v vec[u][i];if(dfn[v] -1){tarjan(v);low[u] min(low[u], low[v]);}else if(vis[v] 1){low[u] min(low[u], dfn[v]);}}if(low[u] dfn[u]){cnt;while(!s.empty()){int temp s.top();s.pop();vis[temp]0;belong[temp]cnt;if(temp u)break;}}
}
int main()
{int a,b,c,d;while(~scanf(%d%d, n, m)){init();for(int i 0; i m; i){scanf(%d%d%d%d, a, b, c, d);vec[2*ac].push_back(2*b1-d);vec[2*bd].push_back(2*a1-c);}for(int i 0; i 2*n; i){if(dfn[i] -1)tarjan(i);}bool flag true;for(int i 0; i n; i){if( belong[2*i] belong[2*i1] ){flagfalse;break;}}puts(flag?YES:NO);}return 0;
}Tarjan缩点拓扑染色
#include cstdio
#include cstring
#include iostream
#include algorithm
using namespace std ;
#define M 4000017
#define N 100017
//a1 和 (a1) 1。a1表示妻子(a1) 1表示丈夫
//连接某边是为了推出矛盾。x-y表示选x则必须选y
//注意方向
struct node
{int s, t;int nxt;
} e[M];
int n, m;
int idx, ans, tp, cont;
int dfn[N],vis[N],low[N],head[N],st[N],belong[N];void add(int s,int t)
{e[cont].s s;e[cont].t t;e[cont].nxt head[s];head[s] cont;
}
void build_grap(int a, int b, int c, int d)//建图
{if(c0 d0)//两个妻子{add(a1, (b1)1);add(b1, (a1) 1);}else if(c0 d1)//妻子和丈夫{add((a1), (b1));add((b1)1, (a1)1);}else if(c1 d0)//丈夫和妻子{add((a1) 1, (b1) 1);add(b1, a1);}else if(c1 d1)//两个丈夫有矛盾{add((a1)1, b1);add((b1)1, a1);}
}
void tarjan(int u)
{dfn[u] low[u] idx;vis[u] 1;st[tp] u;int v ;for(int i head[u]; i ! -1; i e[i].nxt){v e[i].t ;if(!dfn[v]){tarjan(v) ;low[u] min(low[u],low[v]);}else if(vis[v])low[u] min(low[u],dfn[v]);}if(dfn[u] low[u]){ans;while(1){v st[tp--];vis[v] 0;belong[v] ans;if(v u)break;}}
}
bool _2sat()
{memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));idx tp ans 0;for(int i 0; i 2*n; i)if(!dfn[i])tarjan(i) ;for(int i 0; i n; i)if(belong[2*i]belong[(2*i)^1])//矛盾return false ;return true;
}int main()
{int a, b, c, d;while(~scanf(%d%d,n,m)){cont 0;memset(head,-1,sizeof(head));for(int i 0; i m; i){scanf(%d%d%d%d,a,b,c,d);//int u, v;//u a*2c; v b*2d;//add(u, v^1); add(v, u^1);build_grap(a, b, c, d);}if(_2sat())printf(YES\n);elseprintf(NO\n);}return 0 ;
}/**思路每对夫妻代表图中一个结点只有 1、0 两种选择对于有矛盾的夫妻对使其不列席让无矛盾夫妻对的列席即可
对于 m 矛盾关系设 a、b 两对夫妇存在矛盾
若第 a 对的妻子与第 b 对的妻子有矛盾a b 0 0
则 a 的妻子去了 b 的丈夫必须去b 的妻子去了 a 的丈夫必须去a,0,b,1、b,0,a,1添边an,b,bn,a
若第 a 对的妻子与第 b 对的丈夫有矛盾a b 0 1
则 a 的妻子去了 b 的妻子必须去b 的丈夫去了 a 的丈夫必须去a,0,b,0、b,1,a,1添边an,bn,b,a
若第 a 对的丈夫与第 b 对的妻子有矛盾a b 1 0
则 a 的丈夫去了 b 的丈夫必须去b 的妻子去了 a 的妻子必须去a,1,b,1、b,0,a,0,添边a,b,bn,an
若第 a 对的丈夫与第 b 对的丈夫有矛盾a b 1 1
则 a 的丈夫去了 b 的妻子必须去b 的丈夫去了 a 的妻子必须去a,1,b,0、b,1,a,0添边a,bn,b,an*/
#includeiostream
#includecstdio
#includestack
#includecstring
#includealgorithm
using namespace std;
const int N 1e610;
const int dx[] {-1,1,0,0,-1,-1,1,1};
const int dy[] {0,0,-1,1,-1,1,-1,1};
using namespace std;
struct node
{int to,next;
} node[N*2];
int head[N],tot;
int n,m;
int dfn[N],low[N];
bool vis[N];//标记数组
int scc[N];//记录结点i属于哪个强连通分量
int block_cnt;//时间戳
int sig;//记录强连通分量个数
stackint S;
void init()
{tot0;sig0;block_cnt0;memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(scc,0,sizeof(scc));
}
void addnode(int from,int to)
{node[tot].toto;node[tot].nexthead[from];head[from]tot;
}
void Tarjan(int x)
{vis[x]true;dfn[x]low[x]block_cnt;//每找到一个新点纪录当前节点的时间戳S.push(x);//当前结点入栈for(int ihead[x]; i!-1; inode[i].next) //遍历整个栈{int ynode[i].to;//当前结点的下一结点if(!dfn[y]){Tarjan(y);low[x]min(low[x],low[y]);}else if(vis[y])low[x]min(low[x],dfn[y]);}if(dfn[x]low[x]) //满足强连通分量要求{sig;//记录强连通分量个数while(true) //记录元素属于第几个强连通分量{int tempS.top();S.pop();vis[temp]false;scc[temp]sig;if(tempx)break;}}
}
bool twoSAT()
{for(int i1; i2*n; i) //找强连通分量if(!dfn[i])Tarjan(i);for(int i1; in; i)if(scc[i]scc[in])//条件a与!a属于同一连通分量无解return false;return true;
}
int main()
{while( scanf(%d%d,n,m)!EOF(nm)){init();while(m--){int x,y,xVal,yVal;scanf(%d%d%d%d,x,y,xVal,yVal);x;y;if(xVal0yVal0) //x为0或y为0{addnode(xn,y);//x为0,y为1addnode(yn,x);//y为0,x为1}else if(xVal0yVal1) //x为0或y为1{addnode(xn,yn);//x为0,y为0addnode(y,x);//y为1,x为1}else if(xVal1yVal0) //x为1或y为0{addnode(x,y);//x为1,y为1addnode(yn,xn);//y为0,x为0}else if(xVal1yVal1) //x为1或y为1{addnode(x,yn);//x为1,y为0addnode(y,xn);//y为1,x为0}}bool flagtwoSAT();if(!flag)printf(NO\n);elseprintf(YES\n);}return 0;
}
