题意:平面上有n个A发射点和m个B发射点,可以选择安置相应A/B装置,装置范围是圆,自取半径(要求都相同且<=Rmax)。异种要求范围不相交。求装置范围之和(不是并!)。

标程:

 #include<bits/stdc++.h>
using namespace std;
const int N=;
const int inf=0x3f3f3f3f;
typedef long long ll;
int cnt=,n,m,ans,Rx,xa[N],xb[N],yb[N],ya[N],head[N],Head[N],tot,S,T,dis[N];
ll Ans;
queue<int> q;
bitset<N> f[N];
struct node{int to,next,f;}num[N*N];
struct Node{int d,x,y;Node(){} Node(int A,int B,int C){d=A;x=B;y=C;}}p[N*N];
void add(int x,int y,int w)
{
num[++cnt].to=y;num[cnt].next=head[x];num[cnt].f=w;head[x]=cnt;
num[++cnt].to=x;num[cnt].next=head[y];num[cnt].f=;head[y]=cnt;
if (!f[x][y])
for (int i=;i<=T;i++) if (f[i][x]&&!f[i][y]) f[i]|=f[y];
}
void init()
{
for (int i=;i<=T;i++) f[i].reset(),f[i][i]=;
for (int i=;i<=T;i++)
for (int j=head[i];j;j=num[j].next)
if (num[j].f) f[i][num[j].to]=;
for (int i=;i<=T;i++)
for (int j=;j<=T;j++) if (f[i][j]) f[i]|=f[j];
}
int bfs()
{
memset(dis,,sizeof(dis));dis[S]=;q.push(S);
while (!q.empty())
{
int now=q.front();q.pop();
for (int i=head[now];i;i=num[i].next)
if (num[i].f&&!dis[num[i].to]) dis[num[i].to]=dis[now]+,q.push(num[i].to);
}
return dis[T];
}
int dfs(int x,int Min)
{
int tmp=Min;
if (x==T||!Min) return Min;
for (int &i=Head[x];i&&tmp;i=num[i].next)
if (dis[num[i].to]==dis[x]+)
{
int t=dfs(num[i].to,min(tmp,num[i].f));
num[i].f-=t;num[i^].f+=t;tmp-=t;
}
return Min-tmp;
}
int dinic()
{
if (!f[S][T]) return ;
int res=,tmp;
while (bfs())
{
memcpy(Head,head,sizeof(head));
while (tmp=dfs(S,inf)) res+=tmp;
}
init();
return res;
}
int get_dis(int i,int j){return (xa[i]-xb[j])*(xa[i]-xb[j])+(ya[i]-yb[j])*(ya[i]-yb[j]);}
bool cmp(const Node &A,const Node &B){return A.d<B.d;}
int main()
{
scanf("%d%d%d",&n,&m,&Rx);S=n+m+;T=S+;
for (int i=;i<=T;i++) f[i][i]=;
for (int i=;i<=n;i++) add(S,i,);
for (int i=;i<=m;i++) add(i+n,T,);
for (int i=;i<=n;i++) scanf("%d",&xa[i]);
for (int i=;i<=n;i++) scanf("%d",&ya[i]);
for (int i=;i<=m;i++) scanf("%d",&xb[i]);
for (int i=;i<=m;i++) scanf("%d",&yb[i]);
for (int i=;i<=n;i++)
for (int j=;j<=m;j++) p[++tot]=Node(get_dis(i,j),i,j);
p[++tot]=Node(Rx*Rx*,,);
sort(p+,p+tot+,cmp);
for (int i=;i<=tot&&p[i].d<=Rx*Rx*;i++)//从0开始,有可能
{
add(p[i].x,p[i].y+n,);
if (p[i].d!=p[i+].d) ans+=dinic(),Ans=max(Ans,min((ll)max(p[i+].d,p[i].d),Rx*Rx*4ll)*(n+m-ans));//注意取后一个半径进行运算,注意边界!
}
printf("%.4lf\n",(double)Ans*M_PI*0.25);
return ;
}

易错点:1.注意统计圆半径是已连边半径的后一个。因此需要从没有圆冲突的半径开始算。

2.一开始以为是圆半径不相同。题目又又又看错了啊。可能是太久没写题了。

题解:枚举半径+网络流匹配+传递闭包优化

如果某A和某B之间的距离为dis,那么如果取半径>dis/2,该A和该B之间只能取其一。

枚举关键半径n^2。只能取其一,即求最大独立集。我们想到了可以二分图匹配n^3(而边权为1用dinic可以做到n^2.5)。O(n^4.5)。

结束。

用传递闭包在每次网络流结束后统计S到T的可达情况。下一次进去的时候若S->T不可达,那么return 0。这样最多进行n次网络流,bitset优化一下:O(n*(n^3/w+n^2.5))。

最新文章

  1. 浅谈cssText
  2. 移动应用平台的开发环境的发展演变-elcipse与android studio
  3. asp.net C#获取程序文件相关信息
  4. 判断js数据类型和clone
  5. 招聘 微软全球技术支持中心 sql server组
  6. 学习记录008-crond和visudo
  7. Activity是如何挂载Pargment的Day35
  8. [BZOJ 2243] [SDOI 2011] 染色 【树链剖分】
  9. Dragger代码实现
  10. ubuntu下安装xlrd模块,Mysqldb模块
  11. zend framework virtualhost设置方法
  12. hdu 4619 Warm up 2 二分图匹配
  13. 2019南昌邀请赛网络预选赛 J.Distance on the tree(树链剖分)
  14. Yocto和Android编译命令的简化和自动完成的实现
  15. C++实验二——函数重载、函数模板、简单类的定义和实现
  16. 光照构建失败。Swarm启动失败
  17. ansible笔记(5):常用模块之文件操作(二)
  18. Android 第一波
  19. oracle 字符转换成数字
  20. Bootstrap如何禁止响应式布局 不适配

热门文章

  1. 关于第一次将STM32与电脑连接情况
  2. mysql数据库 --表操作
  3. Linux grep return code
  4. 使用net模块创建tcp服务器
  5. windows10,nodejs安装步骤
  6. Development 编程规范
  7. c++ GetAsyncState() 函数
  8. 视频质量评测标准——VMAF
  9. 主席树/线段树模拟归并排序+二分答案(好题)——hdu多校第4场08
  10. NX二次开发-C++ DeleteFile删除文件实例代码