题目链接：http://acm./sdutoj/problem.php?action=showproblem&problemid=1953
好长时间没写过博客了。。今天上英语课闲着无聊，聊天玩的时候有人问到了2-SAT。。突然就想起来了这道题。。。
2-SAT嘛。。比赛的时候居然没想到。。
给定需要满足的m个条件。把每个变量拆为两个点。一般情况下拆为2i和2i+1 分别代表它为真和为假 由于这道题是<1000的。
且正的代表选，负的代表不选。那么我们可以把<999的作为要选的，>999的作为不选的。。
比如，第一组样例中的 1 2 代表他投票赞成1和2 那么，这个图可以转化为加一条有向边999-1 -> 999+2代表(如果不选1，那么一定要选2)。
同理，加一条有向边999-2 -> 999+1代表(如果选不选2，那么一定要选1)。
接下来考虑每个没有赋值的变量Xi，假定他为真，然后沿着有向边标记所有能标记到的节点。。
如果有某个变量对应的两个结点都被标记，那么假设肯定不成立。
代码：
int n, m;vector<int> adj[2001];bool vis[2000][2000];void dfs(int u, int v){vis[u][v] = true;for (int i = 0; i < adj[v].size(); i++){int t = adj[v][i];if(!vis[u][t]) dfs(u, t);}}void init(){memset(vis, false, sizeof (vis));for(int i = 0; i < 2000; i++)adj[i].clear();}int main(){while(~scanf("%d %d", &n, &m)){init();for(int i = 0; i < m; i++){int a, b;scan(a);scan(b);adj[999-a].push_back(999+b);adj[999-b].push_back(999+a);}for(int i = 0; i < 1999; i++)dfs(i, i);bool flag = vis[999+1][999-1];if(flag){puts("no");continue;}for(int i = 2; i <= n; i++){if(vis[999+i][999-i] && vis[999-i][999+i]){flag = true;break;}}if(flag) puts("no");else puts("yes");}return 0;}
如果觉得《SDUT 1953 Idol》对你有帮助，请点赞、收藏，并留下你的观点哦！
