Party

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3619 Accepted Submission(s): 1179

Problem Description 有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问题。这道题应该是2-sat的入门类题目，先是建图，然后强连通缩点，如果一对夫妇在一个强连通分量里面则输出NO。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; const int maxn = 2010; //for dfs() int dfs_clock, scc_cnt; int pre[maxn], sccno[maxn], lowlink[maxn]; stack
        
          S; //for graph. int gn, gm; vector
         
           G[maxn]; void dfs(int u) { pre[u] = lowlink[u] = ++dfs_clock; S.push(u); for(int i = 0; i < (int)G[u].size(); 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(pre, 0, sizeof(pre)); memset(sccno, 0, sizeof(sccno)); memset(lowlink, 0, sizeof(lowlink)); for(int i = 0; i < gn*2; i++) { if(!pre[i]) dfs(i); } } int main() { int a1, a2, c1, c2; int u, v; while(scanf("%d%d", &gn, &gm) != EOF) { for(int i = 0; i < maxn; i++) G[i].clear(); for(int i = 0; i < gm; i++) { scanf("%d%d%d%d", &a1, &a2, &c1, &c2); u = (a1<<1)+c1; v = (a2<<1|1)-c2; G[u].push_back(v); u = (a2<<1) + c2; v = (a1<<1|1)-c1; G[u].push_back(v); } find_scc(gn); bool flag = true; for(int i = 0; i < gn; i++) { u = i<<1; v = i<<1|1; if(sccno[u] == sccno[v]) { flag = false; break; } } if(flag) printf("YES\n"); else printf("NO\n"); } return 0; }

hdu3062Party

Party