gym101201

建立矛盾边，2-SAT
 1 #include<bits/stdc++.h> 
 2 #define Pii pair<int,int>
 3 #define fi first
 4 #define se second
 5 #define maxn 1010
 6 const int MAXN = 20020; 
 7 const int MAXM = 100010;
 8 using namespace std; 
 9 int r;
10 struct Edge {
11      int to,next; 
12 }edge[MAXM]; 
13 int head[MAXN],tot; 
14 void init(){ 
15     tot = 0;    
16     memset(head,-1,sizeof(head)); 
17 }  
18 void addedge(int u,int v){
19     edge[tot].to = v;
20     edge[tot].next = head[u];
21     head[u] = tot++; 
22 } bool vis[MAXN];//染色标记，为true表示选择 
23 int S[MAXN],top;//栈 
24 bool dfs(int u){
25     if(vis[u^1])return false;
26     if(vis[u])return true;     
27     vis[u] = true;     
28     S[top++] = u;     
29     for(int i = head[u];i != -1;i = edge[i].next)
30         if(!dfs(edge[i].to))    
31             return false;    
32     return true; 
33 }
34 bool Twosat(int n){ 
35     memset(vis,false,sizeof(vis));   
36     for(int i = 0;i < n;i += 2){        
37          if(vis[i] || vis[i^1])
38             continue;        
39         top = 0;  
40         if(!dfs(i)){       
41             while(top)
42                 vis[S[--top]] = false;   
43             if(!dfs(i^1)) return false;         
44         }     
45     }     
46     return true; 
47 } 
48 bool check(int x,int y){
49     return (abs(y-x)<=2*r);
50 }
51 Pii seg[maxn];
52 int main(){     
53     int n,m,l;   
54     int u,v;   
55     cin>>n>>r>>l;
56     for(int i=0;i<l;i++){
57         scanf("%d%d",&seg[i].fi,&seg[i].se);
58     }
59     init();
60     for(int i=0;i<l;i++){
61         for(int j=i+1;j<l;j++){
62             if(i==j) continue;
63             if(seg[i].se==seg[j].se&&check(seg[i].fi,seg[j].fi)){
64                 addedge((2*i)^1,2*j);
65                 addedge((2*j)^1,2*i);
66             }
67             if(seg[i].fi==seg[j].fi&&check(seg[i].se,seg[j].se)){
68                 addedge(2*j,(2*i)^1);
69                 addedge(2*i,(2*j)^1);
70             }
71         }
72     } 
73     if(Twosat(2*l)) cout<<"YES";
74     else cout<<"NO";
75     return 0; 
76 }