gym101221I Sensor Network
题意
给定 \(n\) 个点，求最大点集使得点两两之间距离 \(\leq d\)。
题解
很容易将题意转化为 \(x\) 选则 \(y\) 不能选的限制，求最多选的点数。
那么就是一般图最小点覆盖。这个图显然不是二分图， 因为三个两两距离 \(\gt d\) 的点很容易找到。
考虑枚举选出点集的直径。也就是枚举两个点，要求所有点间的距离都不超过这两个点的距离 \(r\)。
容易发现所有点都在以这两个点为圆心半径为 \(r\) 的圆交的区域内。
把这样的点选出来，考虑前面的想法，也就是题意转化为 \(x\) 选则 \(y\) 不能选。此时容易发现在图形中不存在三个两两距离\(\gt r\)的点对。为啥？因为图形按照两个圆心连线分成两块，每一块的直径都不超过\(r\)，也就是不能在一块中选两个点，当然两块加起来就不能选 \(3\) 个点了。
此时图形变成了个二分图(按照在连线哪边决定是黑还是白)，用dinic算最小点覆盖即可。
时间复杂度\(O(n^{4.5})\)。
代码
namespace flow{
const int N=105;
const int M=20005;
int to[M],lst[M],beg[N],w[M],e=1,cur[N],q[N],dis[M];
int n,s,t;
void init(){
for(int i=1;i<=n;++i){beg[i]=0;}
e=1;
}
void add(int u,int v,int c){
to[++e]=v;lst[e]=beg[u];beg[u]=e;w[e]=c;
to[++e]=u;lst[e]=beg[v];beg[v]=e;w[e]=0;
}
bool bfs(){
for(int i=1;i<=n;++i){cur[i]=beg[i];dis[i]=n+1;}
dis[s]=0;
int *l=q,*r=q;
*(l=r=q)=s;
while(l<=r){
for(int i=beg[*l];i;i=lst[i])if(w[i]&&chkmin(dis[to[i]],dis[*l]+1))*(++r)=to[i];
++l;
}
return dis[t]<n;
}
int dfs(int s,int t,int fl){
if(s==t)return fl;
for(int &i=cur[s];i;i=lst[i])if(w[i]&&dis[s]+1==dis[to[i]]){
int v=dfs(to[i],t,min(fl,w[i]));
if(v){w[i]-=v;w[i^1]+=v;return v;}
}
return 0;
}
int calc(){
int flow;
int ans=0;
while(bfs()){
while((flow=dfs(s,t,0x7fffffff)))ans+=flow;
}
return ans;
}
}
int n,w;
pii a[105];
int d[105][105];
vector<int> v1,v2;
int f(pii a,pii b,pii c){
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
signed main(){
#ifdef QAQAutoMaton
freopen("I.in","r",stdin);
freopen("I.out","w",stdout);
#endif
read(n,w);
w=sqr(w);
for(int i=1;i<=n;++i)read(a[i].x,a[i].y);
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)d[i][j]=sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y);
flow::n=n+2;
flow::s=n+1;flow::t=n+2;
int ans=1;
int wx,wy;
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j)if(d[i][j]<=w){
int l=d[i][j];
int c=2;
v1.clear();v2.clear();
flow::init();
for(int k=1;k<=n;++k)if(k!=i && k!=j && d[i][k]<=l&&d[j][k]<=l){
++c;
int lr=f(a[i],a[j],a[k]);
if(lr>0)v1.emplace_back(k);
else if(lr<0)v2.emplace_back(k);
}
for(auto x:v1)flow::add(n+1,x,1);
for(auto y:v2)flow::add(y,n+2,1);
for(int x:v1)for(int y:v2)if(d[x][y]>l)flow::add(x,y,inf);
if(chkmax(ans,c-flow::calc()))wx=i,wy=j;
}
}
write(ans,'\n');
if(ans==1)return write("1\n");
int i=wx,j=wy;
int l=d[i][j];
int c=2;
v1.clear();v2.clear();
flow::init();
write(i,' ',j);
for(int k=1;k<=n;++k)if(k!=i && k!=j && d[i][k]<=l&&d[j][k]<=l){
++c;
int lr=f(a[i],a[j],a[k]);
if(lr>0)v1.emplace_back(k);
else if(lr<0)v2.emplace_back(k);
else write(' ',k);
}
for(auto x:v1)flow::add(n+1,x,1);
for(auto y:v2)flow::add(y,n+2,1);
for(int x:v1)for(int y:v2)if(d[x][y]>l)flow::add(x,y,1);
flow::calc();
using flow::dis;
for(auto x:v1)if(dis[x]!=n+3)write(' ',x);
for(auto y:v2)if(dis[y]==n+3)write(' ',y);
putc('\n');
return 0;
}