[BZOJ1823][JSOI2010]满汉全席（2-SAT）

2019-11-08 01:17:38

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

2-SAT问题首先mx和hx最多选一个然后对于一个评委，栗如mi,hj的话，那么选了hi就必选hj，以此类推

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 2005int T,n,m,cnt,dfs_clock,top,scc;char s1,s2;int tot,point[N],nxt[N],v[N];int pt[N][2],id[N],jd[N],x[N],y[N],dfn[N],low[N],stack[N],belong[N];bool vis[N],flag;void clear(){ n=m=cnt=dfs_clock=top=scc=0; tot=0;memset(point,0,sizeof(point)); memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(belong,0,sizeof(belong));memset(vis,0,sizeof(vis));}void add(int x,int y){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}void tarjan(int x){ dfn[x]=low[x]=++dfs_clock;stack[++top]=x;vis[x]=1; for (int i=point[x];i;i=nxt[i]) if (!dfn[v[i]]) { tarjan(v[i]); low[x]=min(low[x],low[v[i]]); } else if (vis[v[i]]) low[x]=min(low[x],dfn[v[i]]); if (dfn[x]==low[x]) { int now=0;++scc; while (now!=x) { now=stack[top--]; vis[now]=0; belong[now]=scc; } }}int main(){ scanf("%d",&T); while (T--) { clear(); scanf("%d%d/n",&n,&m); cnt=0; for (int i=1;i<=n;++i) pt[i][0]=++cnt,pt[i][1]=++cnt; for (int i=1;i<=m;++i) { scanf("%c%d %c%d/n",&s1,&id[i],&s2,&jd[i]); if (s1=='m') x[i]=0; else x[i]=1; if (s2=='m') y[i]=0; else y[i]=1; add(pt[id[i]][x[i]^1],pt[jd[i]][y[i]]); add(pt[jd[i]][y[i]^1],pt[id[i]][x[i]]); } for (int i=1;i<=n;++i) if (!dfn[i]) tarjan(i); flag=1; for (int i=1;i<=n;++i) { if (!belong[pt[i][0]]&&!belong[pt[i][1]]) continue; if (belong[pt[i][0]]==belong[pt[i][1]]) {flag=0;break;} } if (flag) puts("GOOD"); else puts("BAD"); }}

上一篇：B. Code For 1

下一篇：结束线程的方法

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注