首页 > 代码库 > HDU 1824

HDU 1824

2024-07-12 21:50:05   217人阅读

好吧，这次估计是明白边的含义了。

X\/Y= -X->Y = -Y->X  这就达成了选了-X必须选Y的目的了。对于这道题，必须要明白题目了。

每一个队（三人一队）或者队长留下或者其余两名队员同时留下 ： 就可以得到  X\/(Y^Z)=1 而不是互斥的。

以及  X->-Y     -X->Y

 

 

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7  8 const int MAXN=10010; 9 const int MAXM=100100;10 11 int head[MAXN],dfn[MAXN],low[MAXN],st[MAXN],stop,belong[MAXN],tot,index,pat;12 bool stack[MAXN];13 struct {14     int u,v;15     int next;16 }edge[MAXM];17 int n,m;18 19 void init(){20     stop=0; tot=0; index=0; pat=-1;21     for(int i=0;i<6*n;i++){22         head[i]=-1;23         dfn[i]=low[i]=0;24         belong[i]=-1;25         stack[i]=false;26     }27 }28 29 void addedge(int u,int v){30     edge[tot].u=u;31     edge[tot].v=v;32     edge[tot].next=head[u];33     head[u]=tot++;34 }35 36 void tarjan(int u){37     int v;38     dfn[u]=low[u]=++index;39     st[stop++]=u; stack[u]=true;40     for(int e=head[u];e!=-1;e=edge[e].next){41         v=edge[e].v;42         if(dfn[v]==0){43             tarjan(v);44             low[u]=min(low[u],low[v]);45         }46         else if(stack[v]){47             low[u]=min(low[u],dfn[v]);48         }49     }50     if(dfn[u]==low[u]){51         pat++;52         do{53             v=st[--stop];54             stack[v]=false;55             belong[v]=pat;56         }while(u!=v);57     }58 }59 60 int main(){61     int u,v;62     int a,b,c;63     while(scanf("%d%d",&n,&m)!=EOF){64         init();65         for(int i=1;i<=n;i++){66             scanf("%d%d%d",&a,&b,&c);67             addedge(a*2+1,b*2);68             addedge(a*2+1,c*2);69             addedge(c*2+1,a*2);70             addedge(b*2+1,a*2);71         }72         for(int i=1;i<=m;i++){73             scanf("%d%d",&u,&v);74             addedge(u*2,v*2+1);75             addedge(v*2,u*2+1);76         }77         for(int i=0;i<6*n;i++){78             if(dfn[i]==0)79             tarjan(i);80         }81         bool flag=true;82         for(int i=0;i<3*n;i++){83             if(belong[i*2]==belong[i*2+1]){84                 printf("no\n");85                 flag=false;86                 break;87             }88         }89         if(flag)90         printf("yes\n");91     }92 }
View Code


联系
我们