bzoj4427【Nwerc2015】Cleaning Pipes清理管道

题目描述

Linköping有一个相当复杂的水资源运输系统。在Linköping周围的出水点有一些水井。这些水通过管道输送到其它地点。每条管道是从某一个水井到城市的某个位置的直线管道。

所有管道在地下的深度相同。因此，无论何时，两个管道相交时，它们会形成交点。幸运的是，管道系统正好是以满足两个管道有交点的方式建造。井不计入交点。任何数量的管道（包括零个与超过两个）都可以来源于每一个水井。

这些交点导致了一个问题，因为污垢（石灰和其它东西的混合物）往往会卡住交点，导致管道崩溃和坍塌，导致大型水槽孔的形成。这样的水槽孔对Linköping的学生有吸引的效果，使他们荒废学业，不受教育，这从长远来看将不只是导致管道系统的崩溃，还有社会的结构。因此，当务之急是管道定期清理。北欧提水再分配公司（NWERC） -负责Linköping的水管的 – 拥有充足的机器人车队才可以完成此任务。一个机器人可以在一条管道的开始位置被插入。然后，机器人通过管道一直到结束，并清除沿途所有交点。到达终点后，机器人转身并返回它开始的井。为了防止机器人互相碰撞，政府法规规定每当两个管相交，它们中的至多一个可以包含一个机器人。

由于整个水系统在被清洁时必须关闭（另一政府法规），则NWERC想迅速完成清洗，使用一批次清洁机器人，都必须在同一时间开始。

你的任务是验证是否可以做到这一点 - 即，是否能够把机器人同时插入管道中的一些，在不会有两个机器人相撞的危险下清洁所有交点。

输入格式

输入包括：

第一行两个整数w(1<=w<=1000)和p(1<=p<=1000)，分别表示井的数量和管道的数量。

接下来w行，每行两个整数xi和yi（-10000<=x,y<=10000），表示i号井的位置（井从1到w编号）。

接下来p行，每行3个整数s（1<=s<=w）表示管道从s号井开始，x和y（-10000<=x,y<=10000）表示管道在位置为x，y的点结束。

每条管道都有一个井，就是它开始的那个。被两个或多个管道共享的点是一口井。任两条管道至多会有一个交点。两条管道的公共点可以是他们其中之一或两者的端点。所有管道的长度为正数。

输出格式

If it is possible to clean all intersections as described above, output “possible”. Otherwise, output “impossible”.

如果在上述情况下可以清理所有交点，输出“possible”，否则输出“impossible”。

题解：

题目意思一些射线，端点不算交点，相交的射线只能放一个机器人，问是否有方案让每一个交点都被机器人经过；
如果A和B有交点，那么A放B不放，A不放B一定放，（多个交于一点也是符合题意的），转化成2-sat求解；
翻阅了官解，发现如果有交点A和B连边，二分图判定（因为合法的方案对应了二分图的某一边的点集）；

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N=1010;
 5 int n,m,tot,id[N][2],o=1,hd[N<<1],dfn[N<<1],low[N<<1],idx,st[N<<1],top,bl[N<<1],del[N<<1],cnt;
 6 struct Edge{int v,nt;}E[N*N*2];
 7 struct point{
 8     int x,y;
 9     point(int _x=0,int _y=0):x(_x),y(_y){};
10     point operator +(const point&A)const{return point(x+A.x,y+A.y);}
11     point operator -(const point&A)const{return point(x-A.x,y-A.y);}
12     bool operator ==(const point&A)const{return x==A.x&&y==A.y;}
13     int operator *(const point&A)const{return x*A.x+y*A.y;}
14     int operator ^(const point&A)const{return x*A.y-y*A.x;}
15 }p[N];
16 struct line{point a,b;}l[N];
17 void Adde(int u,int v){E[o]=(Edge){v,hd[u]};hd[u]=o++;}
18 void tarjan(int u){
19     dfn[st[++top]=u]=low[u]=++idx;
20     for(int i=hd[u];i;i=E[i].nt){
21         int v=E[i].v;
22         if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
23         else if(!del[v])low[u]=min(low[u],dfn[v]);
24     }
25     if(dfn[u]==low[u]){
26         int v;cnt++;
27         do{
28             bl[v=st[top--]]=cnt;
29             del[v]=1;
30         }while(v!=u);
31     }
32 }
33 bool judge(int i,int j){
34     if(l[i].a==l[j].a)return false;
35     point a=l[j].a-l[i].a,b=l[j].b-l[i].a,c=l[i].b-l[i].a;
36     if((ll)(c^a)*(c^b)>0)return false;
37     b=l[j].a-l[i].b,c=l[j].b-l[j].a;
38     if((ll)(c^a)*(c^b)>0)return false;
39     return true;
40 }
41 int main(){
42     #ifndef ONLINE_JUDGE
43     freopen("bzoj4427.in","r",stdin);
44     freopen("bzoj4427.out","w",stdout);
45     #endif
46     scanf("%d%d",&n,&m);
47     for(int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);
48     for(int i=1,x;i<=m;i++){
49         scanf("%d",&x);l[i].a=p[x];
50         scanf("%d%d",&l[i].b.x,&l[i].b.y);
51         id[i][0]=++tot;id[i][1]=++tot;
52     }
53     for(int i=1;i<=m;i++)
54     for(int j=i+1;j<=m;j++)if(i!=j&&judge(i,j)){
55         Adde(id[i][0],id[j][1]);
56         Adde(id[i][1],id[j][0]);
57         Adde(id[j][0],id[i][1]);
58         Adde(id[j][1],id[i][0]);
59     }
60     for(int i=1;i<=tot;i++)if(!dfn[i])tarjan(i);
61     int fg=0;for(int i=1;i<=m;i++)if(bl[id[i][0]]==bl[id[i][1]]){fg=1;break;}
62     puts(fg?"impossible":"possible");
63     return 0;
64 }

bzoj4427