首页 > 代码库 > 【BZOJ1822】【JSOI2010】Frozen Nova 冷冻波
【BZOJ1822】【JSOI2010】Frozen Nova 冷冻波
题解:二分答案,然后网络流check。
注意:
理论上来讲,因为如果有
-----------
/ \
/ \
巫妖----小精灵----------------树桩-------
\ /
\ /
\----------- /
这种情况,直接用点到直线距离公式是会错误判断的。
但是读者们请用点到直线距离公式吧。
因为数据貌似是这样的。
不妨把巫妖的目光看成能穿透小精灵吧~(至于能反向发射,不妨想想:地球是圆的!光经过折射自然就可以理解成直线了)
贴个WA了的代码吧:
#include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 600 #define M 1001000 #define inf 10001000 #define eps 1e-5 using namespace std; struct KSD { int v,len,next; }e[M]; int head[N],cnt,rl[M]; void add(int u,int v,int len) { cnt++; e[cnt].v=v; e[cnt].len=rl[cnt]=len; e[cnt].next=head[u]; head[u]=cnt; } int s,t,d[N],maxflow; int n,m,p; struct Point { int x,y,r,t; }ksd[N],ashe[N],garen[N]; bool bfs() { queue<int>q; int i,u,v; memset(d,0,sizeof(d)); q.push(s); d[s]=1; while(!q.empty()) { u=q.front(),q.pop(); for(i=head[u];i;i=e[i].next) { v=e[i].v; if(d[v]||e[i].len==0)continue; d[v]=d[u]+1; if(v==t)return 1; q.push(v); } } return 0; } int dinic(int x,int flow) { if(x==t)return flow; int remain=flow,i,v,k; for(i=head[x];i&&remain;i=e[i].next) { if(d[v=e[i].v]==d[x]+1&&e[i].len) { k=dinic(v,min(remain,e[i].len)); if(!k)d[v]=0; e[i].len-=k,e[i^1].len+=k; remain-=k; } } return flow-remain; } bool check(int mid) { int i,j,k; maxflow=0; for(i=2;i<=cnt;i++)e[i].len=rl[i]; for(i=1;i<=n;i++)e[i<<1].len=mid/ksd[i].t+1; while(bfs())maxflow+=dinic(s,inf); if(maxflow==m)return 1; else return 0; } void build() { int i,j,k; double K,B,D,tx,ty; scanf("%d%d%d",&n,&m,&p); s=n+m+1,t=n+m+2,cnt=1; for(i=1;i<=n;i++)scanf("%d%d%d%d",&ksd[i].x,&ksd[i].y,&ksd[i].r,&ksd[i].t),add(s,i,1),add(i,s,0); for(i=1;i<=m;i++)scanf("%d%d",&ashe[i].x,&ashe[i].y),add(i+n,t,1),add(t,i+n,0); for(i=1;i<=p;i++)scanf("%d%d%d",&garen[i].x,&garen[i].y,&garen[i].r); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { tx=ashe[j].x-ksd[i].x,ty=ashe[j].y-ksd[i].y; if(tx*tx+ty*ty>ksd[i].r*ksd[i].r)continue;// ashe在ksd施法范围外 if(tx>0+eps||tx<0-eps) { K=-ty/tx; B=-K*ksd[i].x-ksd[i].y; for(k=1;k<=p;k++) { D=fabs((K*garen[k].x+garen[k].y+B)/sqrt(K*K+1)); if(D-eps<=garen[k].r)break; } } else { for(k=1;k<=p;k++) { D=fabs(garen[k].x-ksd[i].x); if(D-eps<=garen[k].r)break; } } if(k>p)add(i,j+n,1),add(j+n,i,0); } } } int main() { // freopen("test.in","r",stdin); // freopen("my.out","w",stdout); int i,j,k; build(); int l = 0,r = inf,ans = -1; while(l <= r) { int mid = (l + r) >> 1; if(check(mid)) r = mid - 1,ans = mid; else l = mid + 1; } /*for(i=1;i<=30&&l<=r;i++) { mid=l+r>>1; if(check(mid))ans=mid,r=mid-1; else l=mid+1; }*/ printf("%d\n",ans); return 0; }
【BZOJ1822】【JSOI2010】Frozen Nova 冷冻波
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。