题意

给定 $n$ 个点,求最大点集使得点两两之间距离 $\leq d$。

题解

很容易将题意转化为 $x$ 选则 $y$ 不能选的限制,求最多选的点数。

那么就是一般图最小点覆盖。这个图显然不是二分图, 因为三个两两距离 $\gt d$ 的点很容易找到。

考虑枚举选出点集的直径。也就是枚举两个点,要求所有点间的距离都不超过这两个点的距离 $r$。

容易发现所有点都在以这两个点为圆心半径为 $r$ 的圆交的区域内。

把这样的点选出来,考虑前面的想法,也就是题意转化为 $x$ 选则 $y$ 不能选。此时容易发现在图形中不存在三个两两距离$\gt r$的点对。为啥?因为图形按照两个圆心连线分成两块,每一块的直径都不超过$r$,也就是不能在一块中选两个点,当然两块加起来就不能选 $3$ 个点了。

此时图形变成了个二分图(按照在连线哪边决定是黑还是白),用dinic算最小点覆盖即可。

时间复杂度$O(n^4)$。

代码

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

标签: none

添加新评论