首页 > 代码库 > bzoj 1822: [JSOI2010]Frozen Nova 冷冻波 题解
bzoj 1822: [JSOI2010]Frozen Nova 冷冻波 题解
【原题】
1822: [JSOI2010]Frozen Nova 冷冻波
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 796 Solved: 218
[Submit][Status]
Description
WJJ喜欢“魔兽争霸”这个游戏。在游戏中,巫妖是一种强大的英雄,它的技能Frozen Nova每次可以杀死一个小精灵。我们认为,巫妖和小精灵都可以看成是平面上的点。 当巫妖和小精灵之间的直线距离不超过R,且巫妖看到小精灵的视线没有被树木阻挡(也就是说,巫妖和小精灵的连线与任何树木都没有公共点)的话,巫妖就可以瞬间杀灭一个小精灵。 在森林里有N个巫妖,每个巫妖释放Frozen Nova之后,都需要等待一段时间,才能再次施放。不同的巫妖有不同的等待时间和施法范围,但相同的是,每次施放都可以杀死一个小精灵。 现在巫妖的头目想知道,若从0时刻开始计算,至少需要花费多少时间,可以杀死所有的小精灵?
Input
输入文件第一行包含三个整数N、M、K(N,M,K<=200),分别代表巫妖的数量、小精灵的数量和树木的数量。 接下来N行,每行包含四个整数x, y, r, t,分别代表了每个巫妖的坐标、攻击范围和施法间隔(单位为秒)。 再接下来M行,每行两个整数x, y,分别代表了每个小精灵的坐标。 再接下来K行,每行三个整数x, y, r,分别代表了每个树木的坐标。 输入数据中所有坐标范围绝对值不超过10000,半径和施法间隔不超过20000。
Output
输出一行,为消灭所有小精灵的最短时间(以秒计算)。如果永远无法消灭所有的小精灵,则输出-1。
Sample Input
2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10
Sample Output
5
HINT
Source
JSOI2010第二轮Contest1
【分析】最近刷题有点顺(基本不看题解了)。像这道题,只需二分枚举答案再网络流验证。然而这道题的难点就是如何判断某一“巫妖”到“精灵”是否能打到。实际上就是判断一条直线是否能喝一个圆产生交点。
因为不会向量的运算,我还傻傻地用KX+B的解析式算。然后化成一元二次方程求判别式。然后WA了异常久,后来发现一直被精度卡着。比如圆和直线相切是可行的,然后我就判成有交点,就默认不可行了= =。
PS:除了向量外,还有一种计算方法,就是求圆心到直线的距离和r的关系。
【代码】
#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define INF 2139062143 #define N 405 using namespace std; struct arr{int x,y,r,t;}kill[N],p[N],tree[N]; struct Arr{int go,s,next;}a[N*N]; int end[N],f[N],F[N][N],q[N*100]; const long double eps=1e-6; int n,m,k,i,j,flag,w,error,ans,S,T,cnt; bool get_root() { int x1=kill[i].x,y1=kill[i].y,x2=p[j].x,y2=p[j].y,a=tree[w].x,b=tree[w].y,r=tree[w].r; long double K=(x1==x2)?1e30+0.0:((y1-y2)*1.0/(x1-x2)),B=y1-K*1.0*x1+0.0; long double AA=1.0+1.0*K*K,BB=-2.0*a+2.0*K*(B-b),CC=1.0*a*a+1.0*(B-b)*(B-b)-1.0*r*r; long double temp=BB*BB-4*AA*CC; return (temp>0); //long double aa=K,bb=-1.0,cc=B; //long double dis=(aa*a+bb*b+cc)/sqrt(aa*aa+bb*bb); //return (dis+eps<=r); } inline bool bfs() { memset(f,-1,sizeof(f)); int h=0,t=1;q[1]=S;f[S]=1; while (h<t) { int now=q[++h];if (now==T) return 1; for (int i=end[now];i;i=a[i].next) { int go=a[i].go; if (f[go]==-1&&a[i].s) f[go]=f[now]+1,q[++t]=go; } } return 0; } int dinic(int sta,int sum) { if (sta==T) return sum; int os=sum; for (int i=end[sta];i&&os;i=a[i].next) { int go=a[i].go; if (f[go]==f[sta]+1&&a[i].s) { int Min=dinic(go,min(os,a[i].s)); a[i].s-=Min;a[i^1].s+=Min;os-=Min; } } if (os==sum) f[sta]=-1;return sum-os; } inline void add(int u,int v,int w) { a[++cnt].go=v;a[cnt].s=w;a[cnt].next=end[u];end[u]=cnt; a[++cnt].go=u;a[cnt].s=0;a[cnt].next=end[v];end[v]=cnt; } inline bool check(int Time) { memset(end,0,sizeof(end)); S=0;T=n+m+1;cnt=1;Time++; for (int i=1;i<=n;i++) add(S,i,(Time+kill[i].t-1)/(kill[i].t)); for (int i=1;i<=m;i++) add(n+i,T,1); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (F[i][j]) add(i,n+j,1); int flow=0; while (bfs()) flow+=dinic(S,INF); if (flow<m) return 0;error=0;return 1; } int erfen(int l,int r) { if (l==r) return l; int mid=(l+r)>>1; if (check(mid)) return erfen(l,mid); return erfen(mid+1,r); } inline int dis(arr a,arr b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } int main() { scanf("%d%d%d",&n,&m,&k); for (i=1;i<=n;i++) scanf("%d%d%d%d",&kill[i].x,&kill[i].y,&kill[i].r,&kill[i].t); for (i=1;i<=m;i++) scanf("%d%d",&p[i].x,&p[i].y); for (i=1;i<=k;i++) scanf("%d%d%d",&tree[i].x,&tree[i].y,&tree[i].r); for (i=1;i<=n;i++) for (j=1;j<=m;j++) { flag=1; if (dis(kill[i],p[j])>kill[i].r*kill[i].r) continue; for (w=1;w<=k&&flag;w++) if (get_root()) flag=0; F[i][j]=flag; } error=1;ans=erfen(-1,4000000); if (error) ans=-1;printf("%d",ans); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。