首页 > 代码库 > POJ 3678

POJ 3678

2024-07-13 02:50:33   217人阅读

这道题唯一一个注意的地方是，如出现X\/Y=0这种关系时，X=0,Y=0。已经是可以肯定的关系了，所以可以连边X->-X。

我也错了上面这地方。看来，还不够。以后要细心才好。

 

  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <string.h>  5 #include <algorithm>  6 #include <cmath>  7   8 using namespace std;  9  10 const int MAXN=2050; 11 const int MAXM=4001000; 12 int n,m; 13 char s[10]; 14 int head[MAXN],dfn[MAXN],low[MAXN],st[MAXN],tot,stop,indx,pat,belong[MAXN]; 15 bool stack[MAXN]; 16  17 struct{ 18     int u,v; 19     int next; 20 }edge[MAXM]; 21  22 void addedge(int u,int v){ 23     edge[tot].u=u; 24     edge[tot].v=v; 25     edge[tot].next=head[u]; 26     head[u]=tot++; 27 } 28  29 void tarjan(int u){ 30     int v; 31     dfn[u]=low[u]=++indx; 32     st[stop++]=u; 33     stack[u]=true; 34     for(int e=head[u];e!=-1;e=edge[e].next){ 35         v=edge[e].v; 36         if(dfn[v]==0){ 37             tarjan(v); 38             low[u]=min(low[u],low[v]); 39         } 40         else if(stack[v]){ 41             low[u]=min(low[u],dfn[v]); 42         } 43     } 44     if(dfn[u]==low[u]){ 45         pat++; 46         do{ 47             v=st[--stop]; 48             belong[v]=pat; 49             stack[v]=false; 50         }while(u!=v); 51     } 52 } 53  54 int main(){ 55     int u,v,c; 56     while(scanf("%d%d",&n,&m)!=EOF){ 57          58         memset(head,-1,sizeof(head)); 59         tot=stop=indx=pat=0; 60         memset(dfn,0,sizeof(dfn)); 61         memset(low,0,sizeof(low)); 62         memset(stack,false,sizeof(stack)); 63         memset(belong,0,sizeof(belong)); 64          65         for(int i=0;i<m;i++){ 66             scanf("%d%d%d%s",&u,&v,&c,s); 67             if(strcmp(s,"OR")==0){ 68                 if(c==0){ 69                     addedge(2*u,2*u+1); 70                     addedge(2*v,2*v+1); 71                 } 72                 else{ 73                     addedge(2*u+1,2*v); 74                     addedge(2*v+1,2*u); 75                 } 76             } 77             else if(strcmp(s,"AND")==0){ 78                 if(c==0){ 79                     addedge(2*u,2*v+1); 80                     addedge(2*v,2*u+1); 81                 } 82                 else { 83                     addedge(2*u+1,2*u); 84                     addedge(2*v+1,2*v); 85                 } 86             } 87             else{ 88                 if(c==0){ 89                     addedge(2*u,2*v); 90                     addedge(2*v,2*u); 91                     addedge(2*u+1,2*v+1); 92                     addedge(2*v+1,2*u+1); 93                 } 94                 else{ 95                     addedge(2*u,2*v+1); 96                     addedge(2*u+1,2*v); 97                     addedge(2*v,2*u+1); 98                     addedge(2*v+1,2*u); 99                 }100             }101         }102         for(int i=0;i<2*n;i++){103             if(dfn[i]==0){104                 tarjan(i);105             }106         }107         108         bool flag=true;109         for(int i=0;i<n;i++){110             if(belong[i*2]==belong[2*i+1]){111                 printf("NO\n");112                 flag=false;113                 break;114             }115         }116         if(flag)117         printf("YES\n");118     }119     return 0;120 }
View Code


联系
我们