题目大意:

在游戏中,巫妖是一种强大的英雄,它的技能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个点调了好久以及循环的时候把循环的变量写没了

最新文章

  1. HTML5_03之Canvas绘图
  2. 【转】关于URL编码/javascript/js url 编码/url的三个js编码函数
  3. 【gulp-sass】error: File to import not found or unreadable
  4. Android 模拟登陆 保存密码(信息)到手机中 文件信息读取
  5. CentOS 安装 Tomcat
  6. 流Stream个人学习理解
  7. Android 操作手机内置存储卡中的文件
  8. 一劳永逸让windows 64位操作系统 禁止强制驱动签名
  9. smark和openfire即时通信代码
  10. Java之分支和循环
  11. global,local,static的区别
  12. Python s12 Day2 笔记及作业
  13. tamcat的使用
  14. 记一次改造react脚手架的过程
  15. BASIC-3 字母图形 循环 字符串
  16. 解决vuecli3.0构建的vue2.0项目在IE9可能出现的兼容性问题
  17. spring学习总结——高级装配学习一(profile与@Conditional)
  18. layui与echarts
  19. MybatisPlus使用介绍
  20. PAT (Advanced Level) Practise 1002 解题报告

热门文章

  1. dom4j使用方法详解
  2. java_线程创建的两种方法
  3. 初步认识MVC
  4. qemu vm setup network(ssh) with buildroot
  5. JavaScript--小白入门篇2
  6. [Algorithm] 7. Serialize and Deserialize Binary Tree
  7. manacher(马拉车)算法
  8. linux-vmstat-显示虚拟内存状态
  9. vue axios请求超时,设置重新请求的完美解决方法
  10. 解决Web部署 woff字体 404错误