http://www.lydsy.com/JudgeOnline/problem.php?id=1822
|
RunID |
User |
Problem |
Result |
Memory |
Time |
Language |
Code_Length |
Submit_Time |
|
381251 |
Liu_Ts |
1822 |
Accepted |
2432 kb |
136 ms |
C++ |
3298 B |
2013-04-01 11:22:43 |
题意
N个lich，M个spirit，每个lich有一个cd[i]和一个施法半径r[i];
K棵树，每棵树半径为R[i];
如果spirit在lich的施法半径内，且中间不经过任意一棵树，则可以打到。
每次施法只能打掉一个。
求最少多少时间可以打掉所有spirit。
题解
二分答案x，
网络流验证，
S向每个lich连边，容量为x/cd[i]+1
每个lich向它能打的到的spirit连边；
暴力预处理。
#include<cstring>
#include<climits>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int K=202,N=500,M=100000;
struct point
{
double x,y;
point operator +(const point b)
{
point ans;ans.x=x+b.x;ans.y=y+b.y;
return ans;
}
point operator -(const point b)
{
point ans;ans.x=x-b.x;ans.y=y-b.y;
return ans;
}
double operator *(const point b)
{
double k=x*b.y-b.x*y;
if((-1e-8)<k && k<(1e-8)) return 0;
return k;
}
}lich[K],spirit[K],tree[K];
inline double dist(point a,point b)
{
point p=a-b;
return sqrt(p.x*p.x+p.y*p.y);
}
inline double square(point a,point b,point c)
{
double k=(b-a)*(c-a);
return abs(k);
}
int n,m,k,S,T;
double Rlich[K],Tlich[K],Rtree[K];
bool can[K][K];
bool check(int p,int q)
{
if(Rlich[p]<dist(lich[p],spirit[q])) return 0;
for(int i=1;i<=k;i++)
{
double l=square(lich[p],spirit[q],tree[i])/dist(lich[p],spirit[q]);
if (Rtree[i]-l>(1e-8)) return 0;
}
return 1;
}
int init()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) scanf("%lf%lf%lf%lf",&lich[i].x,&lich[i].y,&Rlich[i],&Tlich[i]);
for(int i=1;i<=m;i++) scanf("%lf%lf",&spirit[i].x,&spirit[i].y);
for(int i=1;i<=k;i++) scanf("%lf%lf%lf",&tree[i].x,&tree[i].y,&Rtree[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(check(i,j)) can[i][j]=true;
S=n+m+1;T=S+1;
}
int u[M],v[M],w[M],next[M],head[N],o;
int low[N],d[N],vd[N],pre[N],cur[N];
void add(int x,int y,int z)
{
u[++o]=x;v[o]=y;w[o]=z;next[o]=head[x];head[x]=o;
u[++o]=y;v[o]=x;w[o]=0;next[o]=head[y];head[y]=o;
}
int solve(int s,int t)
{
memset(cur,0,sizeof(cur));
memset(d,0,sizeof(d));
memset(vd,0,sizeof(vd));
int now=s,ans=0,i;
vd[0]=t;low[s]=INT_MAX;
while(d[s]<t)
{
for(i=cur[now];i;i=next[i])
if(w[i]>0&&d[now]==d[v[i]]+1)
break;
cur[now]=i;
if(i)
{
pre[v[i]]=i;low[v[i]]=min(w[i],low[now]);
now=v[i];
if(now==t)
{
for(;now!=s;now=u[pre[now]])
w[pre[now]]-=low[t],w[pre[now]^1]+=low[t];
low[s]=INT_MAX;ans+=low[t];
}
}
else
{
if(!--vd[d[now]]) break;
d[now]=t;
for(i=head[now];i;i=next[i])
if(w[i]>0&&d[now]>d[v[i]]+1)
d[now]=d[v[i]]+1,cur[now]=i;
vd[d[now]]++;
if(now!=s) now=u[pre[now]];
}
}
return ans;
}
bool work(int x)
{
memset(head,0,sizeof(head));o=1;
for(int i=1;i<=n;i++)
{
add(S,i,x/Tlich[i]+1);
for(int j=1;j<=m;j++)
if(can[i][j])
add(i,n+j,1);
}
for(int i=1;i<=m;i++)
add(n+i,T,1);
return solve(S,T)==m;
}
int main()
{
init();
int l=0,r=10000000,ans=-1;
while(l<=r)
{
int mid=l+r>>1;
if(work(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d\n",ans);
}
