BZOJ 1822[JSOI2010]Frozen Nova 冷冻波

//Twenty#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<cmath>#include<cstring>#include<queue>#include<vector>#define INF 0x3f3f3f3ftypedef long long LL;const int maxn=299*299*2+5;using namespace std;int ans,s,t,n,u,v,w,ecnt=1,fir[maxn],d[maxn],cur[maxn],c[maxn],p[maxn],ed[maxn];struct wuyao{ ???int x,y,r,t;}wy[maxn],jl[maxn],sm[maxn];struct edge { ???int from,to,cap,flow,nxt; ???edge(){} ???edge(int from,int to,int cap,int flow,int nxt):from(from),to(to),cap(cap),flow(flow),nxt(nxt){}}e[maxn];void add(int u,int v,int w) { ???e[++ecnt]=edge(u,v,w,0,fir[u]); ????????e[++ecnt]=edge(v,u,0,0,fir[v]); ????fir[u]=ecnt-1; fir[v]=ecnt;}queue<int>que;void bfs(int s,int t) { ???for(int i=1;i<=n;i++) d[i]=n; ???d[t]=0; ????que.push(t); ???while(!que.empty()) { ???????int x=que.front() ;que.pop(); ???????for(int i=fir[x];i;i=e[i].nxt) ????????if(d[e[i].to]==n&&e[i].flow==e[i].cap) { ???????????d[e[i].to]=d[x]+1; ???????????que.push(e[i].to); ????????} ???}}int cal(int s,int t) { ???int fl=INF; ???for(int x=t;x!=s;x=e[p[x]].from) ????????fl=min(fl,e[p[x]].cap-e[p[x]].flow); ???for(int x=t;x!=s;x=e[p[x]].from) { ???????e[p[x]].flow+=fl; ???????e[p[x]^1].flow-=fl; ???} ???return fl;}int maxflow(int s,int t) { ???bfs(s,t); ???int res=0; ???for(int i=1;i<=n;i++) cur[i]=fir[i],c[d[i]]++; ???for(int x=s;d[x]<n;) { ???????if(x==t) { ???????????res+=cal(s,t); ???????????x=s; ???????} ???????int ok=0; ???????for(int &i=cur[x];i;i=e[i].nxt) ????????????if(d[e[i].to]+1==d[x]&&e[i].cap>e[i].flow){ ???????????????p[x=e[i].to]=i; ???????????????ok=1; break; ???????????} ???????if(!ok) { ???????????cur[x]=fir[x]; int M=n; ???????????for(int i=cur[x];i;i=e[i].nxt) ????????????????if(e[i].cap>e[i].flow) ???????????????????M=min(M,d[e[i].to]+1); ???????????if(!(--c[d[x]])) break; ???????????c[d[x]=M]++; ???????????if(x!=s) x=e[p[x]].from; ???????} ???} ???return res;}double dis(int x,int y,int xx,int yy) { ???return sqrt((double)(x-xx)*(x-xx)+(double)(y-yy)*(y-yy));}double Dis(int x,int y,double A,double B,double C) { ???return fabs((A*x+B*y+C))/sqrt(A*A+B*B);} ???int wys,jls,sms;double yyj;int check(int ti) { ???for(int i=1;i<=ecnt;i++) e[i].flow=0; ???for(int i=1;i<=wys;i++) { ???????int fl=ti/wy[i].t+1; ???????e[ed[i]].cap=fl; ???} ???return (maxflow(s,t)==jls);}int main(){ ???//freopen(".in","r",stdin); ???//freopen(".out","w",stdout); ???scanf("%d%d%d",&wys,&jls,&sms); ???n=wys+jls+2; s=n-1; t=n; ???for(int i=1;i<=wys;i++) { ???????scanf("%d%d%d%d",&wy[i].x,&wy[i].y,&wy[i].r,&wy[i].t); ???????add(s,i,0); ed[i]=ecnt-1; ???} ???for(int i=1;i<=jls;i++) { ???????scanf("%d%d",&jl[i].x,&jl[i].y); ???????add(wys+i,t,1); ???} ???for(int i=1;i<=sms;i++) ????????scanf("%d%d%d",&sm[i].x,&sm[i].y,&sm[i].r); ???????????????for(int i=1;i<=wys;i++) { ???????for(int j=1;j<=jls;j++) ????????????if((yyj=dis(wy[i].x,wy[i].y,jl[j].x,jl[j].y))<=(double)wy[i].r) { ???????????????double A=(wy[i].y-jl[j].y),B=jl[j].x-wy[i].x,C=wy[i].x*jl[j].y-wy[i].y*jl[j].x; ?????????????????if(i==60) { ??????????????????int debug=1; ?????????????????} ???????????????if(!sms) ????????????????????add(i,wys+j,1); ???????????????for(int k=1;k<=sms;k++) { ???????????????????double tmp; ???????????????????double ddx=Dis(sm[k].x,sm[k].y,A,B,C); ???????????????????double zb=dis(wy[i].x,wy[i].y,sm[k].x,sm[k].y),yb=dis(jl[j].x,jl[j].y,sm[k].x,sm[k].y); ???????????????????if(zb<yb) swap(zb,yb); ???????????????????double woc=sqrt(zb*zb-ddx*ddx); ?????????????????????tmp=woc<=yyj?ddx:yb; ???????????????????if(tmp<=(double)sm[k].r) break; ???????????????????if(k==sms) ????????????????????????add(i,wys+j,1); ???????????????} ???????????} ???????} ???????int l=0,r=4e6+5; ???if(!check(r)) ans=-1; ???else { ???????while(l<=r) { ???????????int mid=(l+r)>>1; ???????????if(check(mid)) ans=mid,r=mid-1; ???????????else l=mid+1; ???????} ???} ???printf("%d\n",ans); ???return 0;}