JLOI2014 Day2 T3,一道有趣的 最小割 的题目。
题目链接:Luogu P3260/BZOJ 3630/LibreOJ 2235/JLOI2014 D2T3。
题目
比较长,可以自己去看。
题解
思路
显然,如果光学元件有缝隙的话,光就可以通过,所以这道题目是最小割的裸题。没什么好说的。
代码
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; #define INF 0X3F3F3F3F #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; inline int read(void){ reg bool f=false; reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return f?-res:res; } const int MAXN=300+5; const int MAXV=2*MAXN; const int MAXE=2*(MAXN*MAXN*2+2*MAXN+MAXN); inline ll sqr(reg ll x){ return x*x; } struct Round{ int id; ll x,y,r; inline void Read(reg int i){ id=i; x=read(),y=read(),r=read(); return; } }; struct Square{ int id; ll x1,y1,x2,y2; inline void Read(reg int i){ id=i; x1=read(),y1=read(),x2=read(),y2=read(); return; } }; Round R[MAXN]; Square S[MAXN]; int cnt=1,head[MAXV],to[MAXE],w[MAXE],Next[MAXE]; inline void Add_Edge(reg int u,reg int v,reg int len){ Next[++cnt]=head[u]; to[cnt]=v; w[cnt]=len; head[u]=cnt; return; } inline void Add_Tube(reg int u,reg int v,reg int len){ Add_Edge(u,v,len); Add_Edge(v,u,0); return; } int dep[MAXV]; queue<int> Q; inline bool BFS(int s,reg int t){ memset(dep,-1,sizeof(dep)); while(!Q.empty())Q.pop(); dep[s]=1,Q.push(s); while(!Q.empty()){ reg int u=Q.front(); Q.pop(); for(reg int i=head[u];i;i=Next[i]){ int v=to[i]; if(dep[v]==-1&&w[i]>0){ dep[v]=dep[u]+1; Q.push(v); } } } return dep[t]!=-1; } int cur[MAXV]; inline int DFS(reg int u,reg int t,reg int lim){ if(u==t) return lim; reg int flow=0; for(reg int &i=cur[u];i;i=Next[i]){ reg int v=to[i]; if(dep[v]==dep[u]+1&&w[i]>0){ reg int f=DFS(v,t,min(lim-flow,w[i])); if(f){ flow+=f; w[i]-=f; w[i^1]+=f; if(flow==lim) break; } } } return flow; } inline int Dinic(reg int s,reg int t){ reg int res=0; while(BFS(s,t)){ memcpy(cur,head,sizeof(head)); res+=DFS(s,t,INF); } return res; } int cx,cy; inline bool checkx(const Round& a,const Square& b){ if(min(a.x,b.x1)!=b.x1||max(a.x,b.x2)!=b.x2) return false; if(min(a.y,b.y1)==b.y1&&max(a.y,b.y2)==b.y2) return true; return sqr(a.y-b.y1)<=sqr(a.r)||sqr(a.y-b.y2)<=sqr(a.r); } inline bool checky(const Round& a,const Square& b){ if(min(a.y,b.y1)!=b.y1||max(a.y,b.y2)!=b.y2) return false; return sqr(a.x-b.x1)<=sqr(a.r)||sqr(a.x-b.x2)<=sqr(a.r); } inline bool checkp(const Round& b,const Square& a){ reg ll r2=sqr(b.r); return (sqr(a.x1-b.x)+sqr(a.y1-b.y)<=r2||sqr(a.x1-b.x)+sqr(a.y2-b.y)<=r2||sqr(a.x2-b.x)+sqr(a.y1-b.y)<=r2||sqr(a.x2-b.x)+sqr(a.y2-b.y)<=r2); } inline bool check(const Round& b,const Square& a){ return checkx(b,a)||checky(b,a)||checkp(b,a); } inline bool check(const Round& a,const Round& b){ return sqr(a.r+b.r)>=sqr(a.x-b.x)+sqr(a.y-b.y); } inline bool check(const Square& a,const Square& b){ reg bool fx=min(a.x2,b.x2)>=max(a.x1,b.x1); reg bool fy=min(a.y2,b.y2)>=max(a.y1,b.y1); return fx&&fy; } inline bool checkS(const Round& a){ return cy<=a.y+a.r; } inline bool checkT(const Round& a){ return a.y-a.r<=0; } inline bool checkS(const Square& a){ return cy<=a.y2; } inline bool checkT(const Square& a){ return a.y1<=0; } int n; int main(void){ cx=read(),cy=read(); n=read(); reg int cntR=0,cntS=0; for(reg int i=1;i<=n;++i){ static int type; type=read(); switch(type){ case 1:{ R[++cntR].Read(i); break; } case 2:{ S[++cntS].Read(i); break; } default:break; } } for(reg int i=1;i<=n;++i) Add_Tube(i,i+n,1); for(reg int i=1;i<=cntR;++i) for(reg int j=1;j<=cntS;++j) if(check(R[i],S[j])){ reg int a=R[i].id,b=S[j].id; Add_Tube(a+n,b,INF); Add_Tube(b+n,a,INF); } for(reg int i=1;i<=cntR;++i) for(reg int j=i+1;j<=cntR;++j) if(check(R[i],R[j])){ reg int a=R[i].id,b=R[j].id; Add_Tube(a+n,b,INF); Add_Tube(b+n,a,INF); } for(reg int i=1;i<=cntS;++i) for(reg int j=i+1;j<=cntS;++j) if(check(S[i],S[j])){ reg int a=S[i].id,b=S[j].id; Add_Tube(a+n,b,INF); Add_Tube(b+n,a,INF); } reg int s=0,t=2*n+1; for(reg int i=1;i<=cntR;++i){ if(checkS(R[i])) Add_Tube(s,R[i].id,INF); if(checkT(R[i])) Add_Tube(R[i].id+n,t,INF); } for(reg int i=1;i<=cntS;++i){ if(checkS(S[i])) Add_Tube(s,S[i].id,INF); if(checkT(S[i])) Add_Tube(S[i].id+n,t,INF); } reg int ans=Dinic(s,t); printf("%d\n",ans); return 0; }
近期评论