高橋・直樹's Blog

http://www.lydsy.com/JudgeOnline/problem.php?id=1822

题意

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);
}