时间戳

首页 > 技术文章 > Bzoj1822 [JSOI2010]Frozen Nova 冷冻波

Bzoj1822 [JSOI2010]Frozen Nova 冷冻波

SilverNebula 2017-06-05 20:03 原文

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 1933  Solved: 608

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

Sample Output

5

HINT

Source

JSOI2010第二轮Contest1

 

图论 网络流 计算几何

没什么意义的板子题

 

$O(n^3)$用计算几何判断每个巫妖能攻击到哪些小精灵。只需要判断巫妖到小精灵的连线是否与代表树的圆相离即可。

二分答案，用最大流check限定时间内能否将小精灵消灭完：

　　源点向每个小精灵连边，容量为1;

　　每个小精灵向能攻击到它的巫妖连边，容量为1

　　每个巫妖向汇点连边，容量为限定时间内的最多攻击次数。

　　（注意技能没有开场CD，时间为0时即可攻击）

 

(看上去像是简单的网络流+简单的计算几何凑了一道码农题)

 

——Frozen Nova霜冻新星 怎么翻译成冷冻波这种奇怪的名字啊？   （亡灵族玩家激怒）

——为什么要屠杀小精灵啊？  （NE玩家激怒）

 

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<vector>
  8 #define LL long long
  9 using namespace std;
 10 const int INF=0x3f3f3f3f;
 11 const int mxN=100010;
 12 const int mxn=205;
 13 int read(){
 14     int x=0,f=1;char ch=getchar();
 15     while(ch<'0' || ch>'9'){if(ch=='-')f=-f;ch=getchar();}
 16     while(ch>='0' && ch<='9'){x=x*10-'0'+ch;ch=getchar();}
 17     return x*f;
 18 }
 19 struct edge{
 20     int u,v,nxt,f;
 21 }e[mxN];
 22 int hd[mxn*mxn],mct=1;
 23 int n,m,S,T,d[mxN];
 24 void add_edge(int u,int v,int f){
 25     e[++mct].v=v;e[mct].u=u;e[mct].nxt=hd[u];e[mct].f=f;hd[u]=mct;return;
 26 }
 27 void insert(int u,int v,int f){
 28     add_edge(u,v,f);add_edge(v,u,0);return;
 29 }
 30 //
 31 queue<int>q;
 32 bool BFS(){
 33     for(int i=0;i<=T;i++)d[i]=0;
 34     d[S]=1; q.push(S);
 35     while(!q.empty()){
 36         int u=q.front();q.pop();
 37         for(int i=hd[u];i;i=e[i].nxt){
 38             int v=e[i].v;
 39             if(e[i].f && !d[v]){
 40                 d[v]=d[u]+1;
 41                 q.push(v);
 42             }
 43         }
 44     }
 45     return d[T];
 46 }
 47 int DFS(int u,int lim){
 48     if(u==T)return lim;
 49     int f=0,tmp;
 50     for(int i=hd[u];i;i=e[i].nxt){
 51         int v=e[i].v;
 52         if(e[i].f && d[v]==d[u]+1 && (tmp=DFS(v,min(lim,e[i].f)))){
 53             e[i].f-=tmp;
 54             e[i^1].f+=tmp;
 55             lim-=tmp;
 56             f+=tmp;
 57             if(!lim)return f;
 58         }
 59     }
 60     d[u]=0;
 61     return f;
 62 }
 63 int Dinic(){
 64     int res=0;
 65     while(BFS())res+=DFS(S,INF);
 66     return res;
 67 }
 68 //
 69 struct point{
 70     double x,y;
 71     point(){}
 72     point(double _x,double _y):x(_x),y(_y){}
 73     point operator - (const point &b){return point(x-b.x,y-b.y);}
 74 }lich[mxn],tr[mxn],wisp[mxn];
 75 int range[mxn],CD[mxn],R[mxn];
 76 double Cross(const point &a,const point &b){return a.x*b.y-a.y*b.x;}
 77 double DT(double x){
 78     if(fabs(x)<1e-6)return 0;
 79     return (x>0)?1:-1;
 80 }
 81 double Dist(const point &a,const point &b){
 82     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
 83 }
 84 int K;
 85 //
 86 bool check(int a,int b){
 87     double tmp=Dist(lich[a],wisp[b]);
 88     if(tmp+1e-6>(double)range[a])return 0;
 89     for(int i=1;i<=K;i++){
 90         double res=Cross(wisp[b]-lich[a],tr[i]-lich[a]);
 91         if(DT(res)==0){
 92             if(Dist(lich[a],wisp[b])+R[i]<max(Dist(lich[a],tr[i]),Dist(wisp[b],tr[i])))return 0;
 93             continue;
 94         }
 95         else{
 96             double h=fabs(res)/tmp;
 97             if(h+1e-6<R[i])return 0;
 98         }
 99     }
100     return 1;
101 }
102 //
103 vector<int>ve[mxn];
104 bool vis[mxn];
105 void Build(int lim){
106     memset(hd,0,sizeof hd);mct=1;
107     int i,j;
108     for(i=1;i<=m;i++)insert(S,i,1);
109     for(i=1;i<=n;i++)insert(m+i,T,lim/CD[i]+1);
110     for(i=1;i<=n;i++)
111         for(j=0;j<ve[i].size();j++)
112             insert(ve[i][j],m+i,1);
113     return;
114 }
115 void solve(){
116     S=0;T=n+m+1;
117     int l=0,r=1e7,ans=INF;
118     while(l<=r){
119         int mid=(l+r)>>1;
120         Build(mid);
121         int tmp=Dinic();
122         if(tmp==m){
123             ans=mid;r=mid-1;
124         }else l=mid+1;
125     }
126     printf("%d\n",ans);
127     return;
128 }
129 //
130 
131 int main(){
132 //    freopen("in.txt","r",stdin);
133     int i,j;
134     n=read();m=read();K=read();
135     for(i=1;i<=n;i++){
136         lich[i].x=read();lich[i].y=read();
137         range[i]=read();CD[i]=read();
138     }
139     for(i=1;i<=m;i++){
140         wisp[i].x=read();wisp[i].y=read();
141     }
142     for(i=1;i<=K;i++){tr[i].x=read();tr[i].y=read();R[i]=read();}
143     for(i=1;i<=n;i++)
144         for(j=1;j<=m;j++)
145             if(check(i,j)){
146                 ve[i].push_back(j);
147                 vis[j]=1;
148             }
149     for(i=1;i<=m;i++){
150         if(!vis[i]){
151             printf("-1\n");
152             return 0;
153         }
154     }
155     solve();
156     return 0;
157 }

 

推荐阅读