bzoj 1822 冷冻波
2024-10-01 00:58:50
题目大意:
在游戏中,巫妖是一种强大的英雄,它的技能Frozen Nova每次可以杀死一个小精灵
我们认为,巫妖和小精灵都可以看成是平面上的点。
当巫妖和小精灵之间的直线距离不超过R,且巫妖和小精灵的连线与任何树木都没有公共点,巫妖就可以瞬间杀灭一个小精灵。
在森林里有N个巫妖,每个巫妖释放Frozen Nova之后,都需要等待一段时间,才能再次施放
不同的巫妖有不同的等待时间和施法范围,但相同的是,每次施放都可以杀死一个小精灵。
若从0时刻开始计算,至少需要花费多少时间,可以杀死所有的小精灵
思路:
最大流建图还是比较好想的
但是答案需要二分,然后用最大流判断
连边的时候每个巫妖和它可以消灭的小精灵连一条流量为一的边
每个小精灵和超级汇连一条流量为1的边
每个巫妖和超级源连一条时间(二分得到)/冷却时间+1的流量的边
但是如何判断哪些巫妖和小精灵之间连边呢
需要计(jie)算(xi)几何判断
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define inf 2139062143
#define ll long long
#define MAXN 420
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}
while(isdigit(ch)) x=x*+ch-'',ch=getchar();
return x*f;
}
int n,m,k,r[MAXN],cd[MAXN],R[MAXN],d[MAXN];
struct node {int x,y;}g[MAXN],h[MAXN],tr[MAXN];
double dis(int x1,int y1,int x2,int y2) {return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
int check(node a,node b,int i)
{
if(dis(a.x,a.y,b.x,b.y)>=r[i]) return ;
int A=b.y-a.y,B=a.x-b.x,C=b.x*a.y-a.x*b.y;
for(int l=;l<=k;l++)
{
double dst=fabs(A*tr[l].x+B*tr[l].y+C)/sqrt(A*A+B*B);
double k1,b1,b2,b3;
if(a.x==b.x) b1=a.y,b2=b.y,b3=tr[l].y;
else if(a.y==b.y) b1=a.x,b2=b.x,b3=tr[l].x;
else k1=B/A,b1=a.y-k1*a.x,b2=b.y-k1*b.x,b3=tr[l].y-k1*tr[l].x;
if((b3-b1)*(b3-b2)<=) if(dst<=R[l]) return ;
if(abs(b3-b1)>abs(b3-b2)) if(dis(b.x,b.y,tr[l].x,tr[l].y)<=R[l]) return ;
else if(dis(a.x,a.y,tr[l].x,tr[l].y)<=R[l]) return ;
}
return ;
}
struct dinic
{
int fst[MAXN],nxt[MAXN*MAXN],to[MAXN*MAXN],val[MAXN*MAXN],mp[MAXN][MAXN],cnt,s,t;
void mem() {memset(fst,0xff,sizeof(fst));cnt=-;}
void add(int u,int v,int w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;}
void build(int x)
{
mem();
for(int i=;i<=n;i++) {add(s,i,x/cd[i]+);add(i,s,);}
for(int i=;i<=m;i++) {add(n+i,t,);add(t,n+i,);}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(mp[i][j]) {add(i,n+j,);add(n+j,i,);}
}
int vis[MAXN],tot,cur[MAXN],dep[MAXN],q[MAXN];
int bfs()
{
int l=,r=;
memset(dep,0xff,sizeof(dep));
vis[t]=++tot,q[++r]=t;
while(l<=r)
{
int x=q[l++];
for(int i=fst[x];i!=-;i=nxt[i])
if(val[i^]&&vis[to[i]]!=tot)
{
vis[to[i]]=tot,dep[to[i]]=dep[x]+,q[++r]=to[i];
if(to[i]==s) return ;
}
}
return vis[s]==tot;
}
int dfs(int x,int a)
{
if(x==t||!a) return a;
int flow=,f;
for(int& i=cur[x];i!=-;i=nxt[i])
{
if(val[i]&&dep[to[i]]==dep[x]-&&(f=dfs(to[i],min(a,val[i]))))
{
val[i]-=f,val[i^]+=f,flow+=f,a-=f;
if(!a) break;
}
}
return flow;
}
int solve()
{
int ans=;int f;
while(bfs())
{
for(int i=;i<=n+m+;i++) cur[i]=fst[i];
while(f=dfs(s,inf)) ans+=f;
}
return ans;
}
}D;
int main()
{
n=read(),m=read(),k=read();int mx=-;
for(int i=;i<=n;i++) g[i].x=read(),g[i].y=read(),r[i]=read(),cd[i]=read(),mx=max(mx,cd[i]);
for(int i=;i<=m;i++) {h[i].x=read(),h[i].y=read();D.add(n+i,n+m+,);D.add(n+m+,n+i,);}
for(int i=;i<=k;i++) tr[i].x=read(),tr[i].y=read(),R[i]=read();
D.s=,D.t=n+m+;int f;
for(int j=;j<=m;j++)
{
f=;
for(int i=;i<=n;i++)
{
D.mp[i][j]=check(g[i],h[j],i);
if(D.mp[i][j]) f=;
}
if(!f) {puts("-1");return ;}
}
int l=,r=m*mx,mid;
int ans=inf;
while(l<=r)
{
mid=(l+r)>>;
D.build(mid);
if(D.solve()==m) ans=min(ans,mid),r=mid-;
else l=mid+;
}
printf("%d",ans);
}
对于计算几何非常不熟练,只能用解析几何
写完的时候因为忘记了有n+m+2个点调了好久以及循环的时候把循环的变量写没了
最新文章
- HTML5_03之Canvas绘图
- 【转】关于URL编码/javascript/js url 编码/url的三个js编码函数
- 【gulp-sass】error: File to import not found or unreadable
- Android 模拟登陆 保存密码(信息)到手机中 文件信息读取
- CentOS 安装 Tomcat
- 流Stream个人学习理解
- Android 操作手机内置存储卡中的文件
- 一劳永逸让windows 64位操作系统 禁止强制驱动签名
- smark和openfire即时通信代码
- Java之分支和循环
- global,local,static的区别
- Python s12 Day2 笔记及作业
- tamcat的使用
- 记一次改造react脚手架的过程
- BASIC-3	字母图形	循环 字符串
- 解决vuecli3.0构建的vue2.0项目在IE9可能出现的兼容性问题
- spring学习总结——高级装配学习一(profile与@Conditional)
- layui与echarts
- MybatisPlus使用介绍
- PAT (Advanced Level) Practise 1002 解题报告