Let's go home
Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1616 Accepted Submission(s): 661
Problem Description
小时候,乡愁是一枚小小的邮票,我在这头,母亲在那头。
—— 余光中
集训是辛苦的,道路是坎坷的,休息还是必须的。经过一段时间的训练,lcy决定让大家回家放松一下,但是训练还是得照常进行,lcy想出了如下回家规定,每一个队(三人一队)或者队长留下或者其余两名队员同时留下;每一对队员,如果队员A留下,则队员B必须回家休息下,或者B留下,A回家。由于今年集训队人数突破往年同期最高记录,管理难度相当大,lcy也不知道自己的决定是否可行,所以这个难题就交给你了,呵呵,好处嘛~,免费**漂流一日。
—— 余光中
集训是辛苦的,道路是坎坷的,休息还是必须的。经过一段时间的训练,lcy决定让大家回家放松一下,但是训练还是得照常进行,lcy想出了如下回家规定,每一个队(三人一队)或者队长留下或者其余两名队员同时留下;每一对队员,如果队员A留下,则队员B必须回家休息下,或者B留下,A回家。由于今年集训队人数突破往年同期最高记录,管理难度相当大,lcy也不知道自己的决定是否可行,所以这个难题就交给你了,呵呵,好处嘛~,免费**漂流一日。
Input
第一行有两个整数,T和M,1<=T<=1000表示队伍数,1<=M<=5000表示对数。
接下来有T行,每行三个整数,表示一个队的队员编号,第一个队员就是该队队长。
然后有M行,每行两个整数,表示一对队员的编号。
每个队员只属于一个队。队员编号从0开始。
接下来有T行,每行三个整数,表示一个队的队员编号,第一个队员就是该队队长。
然后有M行,每行两个整数,表示一对队员的编号。
每个队员只属于一个队。队员编号从0开始。
Output
可行输出yes,否则输出no,以EOF为结束。
Sample Input
1 2 0 1 2 0 1 1 2 2 4 0 1 2 3 4 5 0 3 0 4 1 3 1 4
Sample Output
yes no
Author
威士忌
Source
解题思路:
2-SAT就是两者有冲突就连边。
#include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <vector> #include <queue> #include <algorithm> #include <stack> #include <set> #include <map> #define LL long long using namespace std; const int MAXN = 20010; vector<int>G[MAXN]; int pre[MAXN], lowlink[MAXN], sccno[MAXN], dfs_clock, scc_cnt; stack<int> s; void dfs(int u) { pre[u] = lowlink[u] = ++dfs_clock; s.push(u); int sz = G[u].size(); for(int i=0;i<sz;i++) { int v = G[u][i]; if(!pre[v]) { dfs(v); lowlink[u] = min(lowlink[u], lowlink[v]); } else if(!sccno[v]) { lowlink[u] = min(lowlink[u], pre[v]); } } if(lowlink[u] == pre[u]) { scc_cnt++; for(;;) { int x = s.top(); s.pop(); sccno[x] = scc_cnt; if(x == u) break; } } } void find_scc(int n) { dfs_clock = scc_cnt = 0; memset(sccno, 0, sizeof(sccno)); memset(pre, 0, sizeof(pre)); for(int i=1;i<=n;i++) if(!pre[i]) dfs(i); } int N, M, T; int main() { while(scanf("%d%d", &T, &M)!=EOF) { int x, y, z; N = 3 * T; for(int i=0;i<=2*N;i++) G[i].clear(); for(int i=1;i<=T;i++) { scanf("%d%d%d", &x, &y, &z); x++; y++; z++; G[x+N].push_back(y); G[x+N].push_back(z); G[y+N].push_back(x); G[z+N].push_back(x); } for(int i=1;i<=M;i++) { scanf("%d%d", &x, &y); x++; y++; G[x].push_back(y + N); G[y].push_back(x + N); } find_scc(2 * N); int flag = 1; for(int i=1;i<=N;i++) { if(sccno[i] == sccno[i + N]) { flag = 0; break; } } if(flag) puts("yes"); else puts("no"); } return 0; }
有疑问加站长微信联系(非本文作者)