【bzoj3630】镜面通道

  • 本文为博主原创,未经许可不得转载

根据物理上的费马小定理,只要水能通过,光就能通过

所以我们的做法就很显然了

如果两个图形相交,就连一条边

问题就成了删去最少的点使得S与T不连通

拆点最小割即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 500100
#define INF 1e9
using namespace std;
struct node{int opt,x,y,r,x1,y1,x2,y2;}A[MAXN];
struct edge{int y,next,v;}e[MAXN<<1];
int n,m,C,R,len(1),S,T,cnt,Link[MAXN],In[MAXN],Out[MAXN],level[MAXN];
queue<int>q;
inline int read(){
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
void insert(int x,int y,int v){
e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;
e[++len].next=Link[y];Link[y]=len;e[len].y=x;e[len].v=0;
}
double Lenth(int x1,int y1,int x2,int y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
bool check(int i,int j){
int opt=A[i].opt+A[j].opt;
if(opt==2) return Lenth(A[i].x,A[i].y,A[j].x,A[j].y)<=A[i].r+A[j].r?1:0;
if(opt==3){
if(A[i].opt==1) swap(i,j);
if(Lenth(A[i].x1,A[i].y1,A[j].x,A[j].y)<=A[j].r) return 1;
if(Lenth(A[i].x1,A[i].y2,A[j].x,A[j].y)<=A[j].r) return 1;
if(Lenth(A[i].x2,A[i].y1,A[j].x,A[j].y)<=A[j].r) return 1;
if(Lenth(A[i].x2,A[i].y2,A[j].x,A[j].y)<=A[j].r) return 1;
if(A[i].x1<A[j].x&&A[i].x2>A[j].x&&(abs(A[i].y1-A[j].y)<=A[j].r||abs(A[i].y2-A[j].y)<=A[j].r)) return 1;
if(A[i].y1<A[j].y&&A[i].y2>A[j].y&&(abs(A[i].x1-A[j].x)<=A[j].r||abs(A[i].x2-A[j].x)<=A[j].r)) return 1;
if(A[i].x1<=A[j].x&&A[i].x2>=A[j].x&&A[i].y1<=A[j].y&&A[i].y2>=A[j].y) return 1;
return 0;
}
if(opt==4){
if(A[j].x1>=A[i].x1&&A[j].x1<=A[i].x2&&A[j].y1>=A[i].y1&&A[j].y1<=A[i].y2) return 1;
if(A[j].x1>=A[i].x1&&A[j].x1<=A[i].x2&&A[j].y2>=A[i].y1&&A[j].y2<=A[i].y2) return 1;
if(A[j].x2>=A[i].x1&&A[j].x2<=A[i].x2&&A[j].y1>=A[i].y1&&A[j].y1<=A[i].y2) return 1;
if(A[j].x2>=A[i].x1&&A[j].x2<=A[i].x2&&A[j].y2>=A[i].y1&&A[j].y2<=A[i].y2) return 1;
swap(i,j);
if(A[j].x1>=A[i].x1&&A[j].x1<=A[i].x2&&A[j].y1>=A[i].y1&&A[j].y1<=A[i].y2) return 1;
if(A[j].x1>=A[i].x1&&A[j].x1<=A[i].x2&&A[j].y2>=A[i].y1&&A[j].y2<=A[i].y2) return 1;
if(A[j].x2>=A[i].x1&&A[j].x2<=A[i].x2&&A[j].y1>=A[i].y1&&A[j].y1<=A[i].y2) return 1;
if(A[j].x2>=A[i].x1&&A[j].x2<=A[i].x2&&A[j].y2>=A[i].y1&&A[j].y2<=A[i].y2) return 1;
return 0;
}
}
bool bfs(){
memset(level,-1,sizeof(level));
q.push(S); level[S]=0;
while(!q.empty()){
int x=q.front(); q.pop();
for(int i=Link[x];i;i=e[i].next)if(level[e[i].y]==-1&&e[i].v){
level[e[i].y]=level[x]+1; q.push(e[i].y);
}
}
return level[T]>=0;
}
int MAXFLOW(int x,int flow){
if(x==T) return flow;
int d=0,maxflow=0;
for(int i=Link[x];i&&maxflow<flow;i=e[i].next)
if(level[e[i].y]==level[x]+1&&e[i].v)
if(d=MAXFLOW(e[i].y,min(flow-maxflow,e[i].v))){
e[i].v-=d; e[i^1].v+=d; maxflow+=d;
}
if(!maxflow) level[x]=-1;
return maxflow;
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
C=read(); R=read();
n=read(); S=++cnt; T=++cnt;
A[0]=(node){2,0,0,0,0,R,C,R};
A[n+1]=(node){2,0,0,0,0,0,C,0};
for(int i=1;i<=n;++i){
In[i]=++cnt;
Out[i]=++cnt;
insert(In[i],Out[i],1);
}
for(int i=1;i<=n;++i){
int opt=read();
if(opt==1){
int x=read(),y=read(),r=read();
A[i]=(node){opt,x,y,r,0,0,0,0};
}
else{
int x1=read(),y1=read(),x2=read(),y2=read();
A[i]=(node){opt,0,0,0,x1,y1,x2,y2};
}
for(int j=1;j<i;++j) if(check(i,j)) insert(Out[i],In[j],INF),insert(Out[j],In[i],INF);
}
for(int i=1;i<=n;++i) if(check(0,i)) insert(S,In[i],INF);
for(int i=1;i<=n;++i) if(check(i,n+1)) insert(Out[i],T,INF);
int d=0,ans=0;
while(bfs()) while(d=MAXFLOW(S,INF)) ans+=d;
printf("%d\n",ans);
return 0;
}
文章目录
,