最小点割集(网络流) JLOI2014 镜面通道

 1 #include <bits/stdc++.h>
 2 #define M 300000
 3 #define N 700
 4 #define inf 100000000
 5 #define eps 0.000000001
 6 using namespace std;
 7 int a[M],b[M],c[M],next[M],g[N],d[N],f[N],r[305],ax[305],bx[305],ay[305],by[305],ty[305],nn,mm,n,m=1,S,T,ans;
 8 double dis(int a,int b,int c,int d){return sqrt((a-c)*(a-c)+(b-d)*(b-d));}
 9 int check(int i,int j){
10     if (i==j) return 0;
11     int v=ty[i]|ty[j];
12     if (v==1){
13         if (dis(ax[i],ay[i],ax[j],ay[j])<=r[i]+r[j]+eps) return 1; 
14     }else
15     if (v==2){
16         if ((ax[i]>=ax[j]&&ax[i]<=bx[j]||bx[i]>=ax[j]&&bx[i]<=bx[j])&&(ay[j]>=ay[i]&&ay[j]<=by[i]||by[j]>=ay[i]&&by[j]<=by[i])) return 1;
17         if ((ay[i]>=ay[j]&&ay[i]<=by[j]||by[i]>=ay[j]&&by[i]<=by[j])&&(ax[j]>=ax[i]&&ax[j]<=bx[i]||bx[j]>=ax[i]&&bx[j]<=bx[i])) return 1;
18     }else{
19         if (ty[i]==2) swap (i,j);
20         if (dis(ax[i],ay[i],ax[j],ay[j])<=r[i]+eps) return 1;
21         if (dis(ax[i],ay[i],ax[j],by[j])<=r[i]+eps) return 1;
22         if (dis(ax[i],ay[i],bx[j],ay[j])<=r[i]+eps) return 1;
23         if (dis(ax[i],ay[i],bx[j],by[j])<=r[i]+eps) return 1;
24         if (ax[i]>=ax[j]&&ax[i]<=bx[j])
25         if (abs(ay[i]-ay[j])<=r[i]||abs(ay[i]-by[j])<=r[i]) return 1;
26         if (ay[i]>=ay[j]&&ay[i]<=by[j])
27         if (abs(ax[i]-ax[j])<=r[i]||abs(ax[i]-bx[j])<=r[i]) return 1;
28     } return 0;
29 }
30 void add(int i,int j,int k){
31     ++m; a[m]=i; b[m]=j; c[m]=k;
32     next[m]=g[i]; g[i]=m;
33     ++m; a[m]=j; b[m]=i; c[m]=0;
34     next[m]=g[j]; g[j]=m;
35 }
36 int spfa(){
37     for (int i=0;i<=T+1;++i)f[i]=-1;
38     d[1]=S; f[S]=0;
39     for (int l=1,r=2;l<r;++l){
40         for (int i=g[d[l]];i;i=next[i])
41             if (c[i]&&f[b[i]]==-1){
42                 f[b[i]]=f[d[l]]+1;
43                 d[r++]=b[i];
44             }
45     }
46     if (f[T]==-1) return 0; return 1;
47 }
48 int flow(int x,int ff){
49     if (x==T) return ff;
50     int use=0; int w;
51     for (int i=g[x];i;i=next[i])
52     if (c[i]&&f[b[i]]==f[x]+1){
53         w=flow(b[i],min(c[i],ff-use));
54         c[i]-=w; c[i^1]+=w; use+=w;
55         if (use==ff) return ff;
56     }
57     if (!use) f[x]=-1; return use;
58 }
59 int main(){
60     scanf("%d%d%d",&nn,&mm,&n); 
61     for (int i=1;i<=n;++i){
62         scanf("%d",&ty[i]); 
63         ty[i]==1?scanf("%d%d%d",&ax[i],&ay[i],&r[i]):
64         scanf("%d%d%d%d",&ax[i],&ay[i],&bx[i],&by[i]);
65     }
66     ty[n+1]=ty[0]=2; by[0]=ay[0]=mm; bx[0]=bx[n+1]=nn;
67     for (int i=0;i<=n+1;++i){
68         for (int j=0;j<=n+1;++j)
69         if (check(i,j)) add(i<<1|1,j<<1,inf); 
70     }
71     for (int i=1;i<=n;++i){
72         add(i<<1|1,i<<1,1);
73         add(i<<1,i<<1|1,1);
74     }
75     S=1; T=n+1<<1;
76     while (spfa()) ans+=flow(S,inf);
77     printf("%d",ans);
78     return 0;
79 }