首页 > 代码库 > BZOJ 1822 Frozen Nova 冷冻波(最大流)
BZOJ 1822 Frozen Nova 冷冻波(最大流)
题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1822
题意:WJJ喜欢“魔兽争霸”这个游戏。在 游戏中,巫妖是一种强大的英雄,它的技能Frozen Nova每次可以杀死一个小精灵。我们认为,巫妖和小精灵都可以看成是平面上的点。 当巫妖和小精灵之间的直线距离不超过R,且巫妖看到小精灵的视线没有被树木阻挡(也就是说,巫妖和小精灵的连线与任何树木都没有公共点)的话,巫妖就可以 瞬间杀灭一个小精灵。 在森林里有N个巫妖,每个巫妖释放Frozen Nova之后,都需要等待一段时间,才能再次施放。不同的巫妖有不同的等待时间和施法范围,但相同的是,每次施放都可以杀死一个小精灵。 现在巫妖的头目想知道,若从0时刻开始计算,至少需要花费多少时间,可以杀死所有的小精灵?
思路:预处理每个巫妖可以杀死的精灵。之后 二分答案最大流判可行性。但是我觉得这个数据有问题。下面这个预处理是用的别人的。我原来写的是WA。但是我觉得这个预处理是有bug的。他是直接相当于 求树到巫妖和精灵连线的距离小于树的半径。但是我觉得这个不对的。比如巫妖和精灵在树的同一侧。
struct node{ int v,cap,next;}; node edges[N*N];int head[N],e; void add(int u,int v,int cap){ edges[e].v=v; edges[e].cap=cap; edges[e].next=head[u]; head[u]=e++;} void Add(int u,int v,int cap){ add(u,v,cap); add(v,u,0);} int cur[N],h[N],num[N],pre[N]; int Maxflow(int s,int t,int n){ int i; for(i=0;i<=n;i++) h[i]=num[i]=0,cur[i]=head[i]; int u=s,ans=0,Min,k,x; while(h[u]<n) { if(u==t) { Min=INF+1; for(i=s;i!=t;i=edges[cur[i]].v) { x=cur[i]; if(edges[x].cap<Min) Min=edges[x].cap,k=i; } ans+=Min; u=k; for(i=s;i!=t;i=edges[cur[i]].v) { x=cur[i]; edges[x].cap-=Min; edges[x^1].cap+=Min; } } for(i=cur[u];i!=-1;i=edges[i].next) { if(edges[i].cap>0&&h[u]==1+h[edges[i].v]) { break; } } if(i!=-1) { cur[u]=i; pre[edges[i].v]=u; u=edges[i].v; } else { if(--num[h[u]]==0) break; cur[u]=head[u]; x=n; for(i=head[u];i!=-1;i=edges[i].next) { k=edges[i].v; if(edges[i].cap>0&&h[k]<x) x=h[k]; } h[u]=x+1; num[x+1]++; if(u!=s) u=pre[u]; } } return ans;} struct A{ int x,y,r,t; void get() { RD(x,y); RD(r,t); }}; A a[N]; struct B{ int x,y; void get() { RD(x,y); } }; B b[N]; struct C{ int x,y,r; void get() { RD(x,y,r); }}; C c[N]; int n,m,K;vector<int> V[N]; int dis(int x,int y){ return x*x+y*y;} int check(A pa,B pb,C pc){ double a=sqrt(dis(pa.x-pb.x,pa.y-pb.y)*1.0); double b=sqrt(dis(pc.x-pb.x,pc.y-pb.y)*1.0); double c=sqrt(dis(pa.x-pc.x,pa.y-pc.y)*1.0); double p=(a+b+c)/2; double s=sqrt(p*(p-a)*(p-b)*(p-c)); double tmp=a*pc.r/2; if(tmp>=s) return 0; return 1;} void init(){ int i,j,k; FOR1(i,n) FOR1(j,m) { if(dis(a[i].x-b[j].x,a[i].y-b[j].y)>a[i].r*a[i].r) continue; FOR1(k,K) if(!check(a[i],b[j],c[k])) break; if(k>K) V[i].pb(j); }}int OK(int mid){ clr(head,-1); e=0; int s=0,t=n+m+1,i,j,k; FOR1(i,n) Add(s,i,mid/a[i].t+1); FOR1(i,m) Add(n+i,t,1); FOR1(i,n) FOR0(j,SZ(V[i])) { k=V[i][j]; Add(i,n+k,1); } return Maxflow(s,t,t+1)==m;} int main(){ RD(n,m,K); int i,j; FOR1(i,n) a[i].get(); FOR1(i,m) b[i].get(); FOR1(i,K) c[i].get(); init(); int low=0,high=INF,mid,ans=-1; while(low<=high) { mid=(low+high)>>1; if(OK(mid)) ans=mid,high=mid-1; else low=mid+1; } PR(ans);}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。