【BZOJ5316】[JSOI2018]绝地反击（网络流，计算几何，二分）

题面

题解

很明显需要二分一个答案。

那么每个点可以确定的范围就是以当前点为圆心，二分出来的答案为半径画一个圆，和目标的圆的交就是可行的区间。

首先我们不知道正\(n\)边形的转角，如果我们知道的话，可以直接暴力网络流来进行\(check\)。

首先一个答案可行，意味着某个点在目标圆上覆盖的弧的两端中，一定有一个是可行的。

所以我们需要验证的转角只有\(2n\)个。这样子暴力跑网络流的次数是\(2nlogn\)次。

考虑如何优化这个过程。

发现合法的转角一共\(2n\)个，把它们按照转角排序，考虑从小往大改变转角的过程，显然每次会删掉一个可行的匹配，或者是加入一组可行的匹配。

那么这里删边直接退流就好了，不需要每次构图重建。

因为是二分图，退流直接手动删边就行了。

加边直接加完之后重新增广一次就行了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<queue>

using namespace std;

#define MAX 605

const double Pi=acos(-1),eps=1e-8;

const int inf=1000000000;

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,R,S,T;

struct Line{int v,next,w;}e[MAX*MAX];

int h[MAX],cnt=2,cur[MAX];

inline void Add(int u,int v,int w)

{

	e[cnt]=(Line){v,h[u],w};h[u]=cnt++;

	e[cnt]=(Line){u,h[v],0};h[v]=cnt++;

}

int level[MAX];

bool bfs()

{

	for(int i=S;i<=T;++i)level[i]=0;

	for(int i=S;i<=T;++i)cur[i]=h[i];

	queue<int> Q;level[S]=1;Q.push(S);

	while(!Q.empty())

	{

		int u=Q.front();Q.pop();

		for(int i=h[u];i;i=e[i].next)

			if(e[i].w&&!level[e[i].v])

				level[e[i].v]=level[u]+1,Q.push(e[i].v);

	}

	return level[T];

}

int dfs(int u,int flow)

{

	if(u==T||!flow)return flow;

	int ret=0;

	for(int &i=cur[u];i;i=e[i].next)

	{

		int v=e[i].v,d=0;

		if(e[i].w&&level[v]==level[u]+1)

		{

			d=dfs(v,min(flow,e[i].w));

			ret+=d;flow-=d;

			e[i].w-=d;e[i^1].w+=d;

			if(!flow)break;

		}

	}

	if(!flow)level[u]=0;

	return ret;

}

void Delete(int u,int v,int &flow)

{

	int val=0;

	for(int i=h[v],j=0;i;j=i,i=e[i].next)

		if(e[i].v==u){j?(e[j].next=e[i].next):(h[v]=e[i].next);break;}

	for(int i=h[u],j=0;i;j=i,i=e[i].next)

		if(e[i].v==v){j?(e[j].next=e[i].next):(h[u]=e[i].next);val=e[i].w^1;break;}

	if(!val)return;--flow;

	for(int i=h[S];i;i=e[i].next)if(e[i].v==u){e[i].w^=1,e[i^1].w^=1;break;}

	for(int i=h[T];i;i=e[i].next)if(e[i].v==v){e[i].w^=1,e[i^1].w^=1;break;}

	if(bfs())flow+=dfs(S,inf);

}

struct Point{double x,y;}p[MAX];

struct Degree{double t;int u,v,opt;}q[MAX];

bool operator<(Degree a,Degree b){return a.t!=b.t?a.t<b.t:a.opt>b.opt;}

double alpha;

bool check(double mid)

{

	for(int i=S;i<=T;++i)h[i]=0;cnt=2;

	int tot=0;

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

	{

		double dis=sqrt(p[i].x*p[i].x+p[i].y*p[i].y);

		if(dis>R+mid||dis<R-mid)return false;

		if(dis+R<=mid)

			for(int j=1;j<=n;++j)Add(i,j+n,1);

		else

		{

			double ang=atan2(p[i].y,p[i].x);

			double d=acos((1.0*R*R+dis*dis-mid*mid)/(2*R*dis));

			double l=ang-d,r=ang+d;

			while(l<0)l+=2*Pi;while(r<0)r+=2*Pi;

			int L=l/alpha,R=r/alpha;

			q[++tot]=(Degree){l-L*alpha,i,L+1,1};

			q[++tot]=(Degree){r-R*alpha,i,R+1,-1};

			++L,++R;

			if(l<=r)

				for(int j=L+1;j<=R;++j)Add(i,j+n,1);

			else

			{

				for(int j=L+1;j<=n;++j)Add(i,j+n,1);

				for(int j=1;j<=R;++j)Add(i,j+n,1);

			}

		}

	}

	for(int i=1;i<=n;++i)Add(S,i,1),Add(i+n,T,1);

	sort(&q[1],&q[tot+1]);int ans=0;

	while(bfs())ans+=dfs(S,inf);

	if(ans==n)return true;

	for(int i=1;i<=tot;++i)

		if(q[i].opt==1)

		{

			Add(q[i].u,q[i].v+n,1);

			if(bfs())ans+=dfs(S,inf);

			if(ans==n)return true;

		}

		else Delete(q[i].u,q[i].v+n,ans);

	return false;

}

int main()

{

	n=read();R=read();alpha=2*Pi/n;

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

	for(int i=1;i<=n;++i)p[i].x=read(),p[i].y=read();

	double l=0,r=400;

	while(r-l>eps)

	{

		double mid=(l+r)/2;

		if(check(mid))r=mid;

		else l=mid;

	}

	printf("%.8lf\n",l);

	return 0;

}

巴特西

【BZOJ5316】[JSOI2018]绝地反击（网络流，计算几何，二分）

【BZOJ5316】[JSOI2018]绝地反击（网络流，计算几何，二分）

题面

题解

最新文章

热门文章