首页 > 代码库 > POJ 3207

POJ 3207

2024-07-13 02:19:03   220人阅读

还是那句话，做2SAT题时，找出矛盾点基本上可解了。这道题也是这样

题意是说给出一个圆上的 n 个点（0~n-1编号），然后在指定的 m 对点之间各连一条线（可以在圆内，也可以在圆外，可以是曲线，这点真心坑爹，开始一直木有看明白），然后问你是否能使这些线都不相交

当两条线在同一边会有交点时，即会有矛盾，建图加边。

对于那些没有交点即没有矛盾的边，直接忽略就好，因为边的含义是“必须”。

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


联系
我们