【BZOJ1822】[JSOI2010]Frozen Nova 冷冻波 几何+二分+网络流

时间：2021-01-04 20:03:58

【BZOJ1822】[JSOI2010]Frozen Nova 冷冻波

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

题解：先判断哪些巫妖能杀死哪些小精灵，然后做法就跟dance那道题一样，直接二分答案，然后跑网络流判定就好了

具体建边方法：设二分答案mid，巫妖攻击间隔t[i]

1.S->巫妖i 容量mid/t[i]+1
2.巫妖i->小精灵j 容量1
3.小精灵j->T 容量1

然后就是怎么判断巫妖i能不能打到小精灵j的问题了

你可能需要这个东西

点到线段的距离，点到直线的距离公式

#include <cstdio>

#include <cstring>

#include <iostream>

#include <queue>

#define n2(_) ((_)*(_))

using namespace std;

typedef long long ll;

int n,m,k,cnt,S,T,ans,tot;

int to[500010],next[500010],val[500010],head[500],d[500],map[210][210],pf[210],pt[210];

ll px[210],py[210],qx[210],qy[210],tx[210],ty[210],tr[210];

queue<int> q;

int dfs(int x,int mf)

{

	if(x==T)	return mf;

	int i,k,temp=mf;

	for(i=head[x];i!=-1;i=next[i])

	{

		if(d[to[i]]==d[x]+1&&val[i])

		{

			k=dfs(to[i],min(temp,val[i]));

			if(!k)	d[to[i]]=0;

			val[i]-=k,val[i^1]+=k,temp-=k;

			if(!temp)	break;

		}

	}

	return mf-temp;

}

int bfs()

{

	memset(d,0,sizeof(d));

	while(!q.empty())	q.pop();

	int i,u;

	q.push(S),d[S]=1;

	while(!q.empty())

	{

		u=q.front(),q.pop();

		for(i=head[u];i!=-1;i=next[i])

		{

			if(val[i]&&!d[to[i]])

			{

				d[to[i]]=d[u]+1;

				if(to[i]==T)	return 1;

				q.push(to[i]);

			}

		}

	}

	return 0;

}

void add(int a,int b,int c)

{

	to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;

	to[cnt]=a,val[cnt]=0,next[cnt]=head[b],head[b]=cnt++;

}

int solve(int sta)

{

	int i,j,l;

	cnt=0,ans=0,tot=0;

	memset(head,-1,sizeof(head));

	S=0,T=n+m+1;

	for(i=1;i<=n;i++)	add(S,i,sta/pt[i]+1),tot+=sta/pt[i]+1;

	if(tot<m)	return 0;

	for(i=1;i<=m;i++)	add(i+n,T,1);

	for(i=1;i<=n;i++)

		for(j=1;j<=m;j++)

			if(map[i][j])

				add(i,j+n,1);

	while(bfs())	ans+=dfs(S,1<<30);

	return ans==m;

}

int main()

{

	scanf("%d%d%d",&n,&m,&k);

	int i,j,l,r=0,mid;

	for(i=1;i<=n;i++)	scanf("%lld%lld%lld%lld",&px[i],&py[i],&pf[i],&pt[i]),r=max(r,pt[i]);

	for(i=1;i<=m;i++)	scanf("%lld%lld",&qx[i],&qy[i]);

	for(i=1;i<=k;i++)	scanf("%lld%lld%lld",&tx[i],&ty[i],&tr[i]);

	for(i=1;i<=n;i++)

	{

		for(j=1;j<=m;j++)

		{

			if(n2(qx[j]-px[i])+n2(qy[j]-py[i])>n2(pf[i]))	continue;

			for(l=1;l<=k;l++)

			{

				ll a=(tx[l]-px[i])*(qx[j]-px[i])+(ty[l]-py[i])*(qy[j]-py[i]),b,c=tr[l]*tr[l];

				if(a<=0)	b=n2(tx[l]-px[i])+n2(ty[l]-py[i]);

				else if(a>=n2(qx[j]-px[i])+n2(qy[j]-py[i]))

					b=n2(tx[l]-qx[j])+n2(ty[l]-qy[j]);

				else	b=n2((qy[j]-py[i])*tx[l]+(px[i]-qx[j])*ty[l]+qx[j]*py[i]-px[i]*qy[j]),

					c*=n2(qy[j]-py[i])+n2(px[i]-qx[j]);

				if(b<c)	break;

			}

			if(l==k+1)	map[i][j]=1;

		}

	}

	l=0,r=4000001,mid;

	while(l<r)

	{

		mid=l+r>>1;

		if(solve(mid))	r=mid;

		else	l=mid+1;

	}

	if(r==4000001)	printf("-1");

	else	printf("%d",r);

	return 0;

}

相关文章