HDU3062 PARTY

怼烎@ 2021-11-10 14:58 202阅读 0赞

# Party #

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

\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<iostream>
     3 #include<cstring>
     4 #include<algorithm>
     5 using namespace std;
     6 const int maxn=1005;
     7 bool bz;
     8 int n,m;
     9 struct edge
    10 {
    11     int u,v,nxt;
    12 }e[maxn*maxn];
    13 int head[maxn<<1],js;
    14 void addage(int u,int v)
    15 {
    16     e[++js].u=u;e[js].v=v;
    17     e[js].nxt=head[u];head[u]=js;
    18 }
    19 int dfn[maxn<<1],low[maxn<<1],cnt,st[maxn<<1],top,lts,lt[maxn<<1];
    20 void init()
    21 {
    22     memset(head,0,sizeof head);
    23     js=0;
    24     memset(dfn,0,sizeof dfn);
    25     memset(low,0,sizeof low);
    26     cnt=0;
    27     top=0;
    28     lts=0;
    29     memset(lt,0,sizeof lt);
    30     bz=1;
    31 }
    32 void tarjan(int u)
    33 {
    34     low[u]=dfn[u]=++cnt;
    35     st[++top]=u;
    36     for(int i=head[u];i;i=e[i].nxt)
    37     {
    38         int v=e[i].v;
    39         if(!dfn[v])
    40         {
    41             tarjan(v);
    42             low[u]=min(low[u],low[v]);
    43         }
    44         else if(!lt[v]) low[u]=min(low[u],dfn[v]);
    45     }
    46     if(low[u]==dfn[u])
    47     {
    48         lt[u]=++lts;
    49         while(st[top]!=u)lt[st[top--]]=lts;
    50         --top;
    51     }
    52 }
    53 int main()
    54 {
    55     while(scanf("%d%d",&n,&m)==2)
    56     {
    57         init();
    58         for(int a,b,c,d,i=1;i<=m;++i)
    59         {
    60             scanf("%d%d%d%d",&a,&b,&c,&d);
    61             ++a;++b;
    62             addage(a+c*n,b+(d^1)*n);
    63             addage(b+d*n,a+(c^1)*n);
    64         }
    65         for(int i=1;i<=(n<<1);++i)
    66             if(!dfn[i])tarjan(i);
    67         for(int i=1;i<=n;++i)
    68             if(lt[i]==lt[i+n])
    69             {
    70                 puts("NO");
    71                 bz=0;
    72                 break;
    73             }
    74         if(bz)puts("YES");
    75     }
    76     return 0;
    77 }

转载于:https://www.cnblogs.com/gryzy/p/10960161.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/3af4ac9bd5fc448f89882037b8e75209.png