题解 P6900 【[ICPC2014 WF]Sensor Network】

Froggy · 2020-10-31 18:48:30 · 题解

Sol 1：乱搞

爆搜/模拟退火/……

暴力求最大团，其实就是这题-> 外太空旅行

Sol 2：正经做法：

放到平面上，其实就有优秀的多项式做法了。

枚举最大团最远的点对，如果两点之间连一条直线，剩下的可用的点就被分到两个区域内。如果把这些点中不能同时被选的点连一条边，容易发现这是个二分图，因为区域内部的点之间不可能连边。

放个图更好理解一点：（两个黑点是钦定的最远点对）

然后求二分图最大独立集即可。

时间复杂度应该的 \mathcal{O}(n^{4.5}) 的吧，反正常数极小跑的飞快。

code:

const int inf=0x3f3f3f3f;
#define N 155
namespace Maxflow{
    int cnt,S,T,dep[N],head[N],pre[N];
    struct Edge{
        int to,nxt,val;
    }edge[N*N<<1];
    void Clear(){
        memset(head,0,sizeof(head));
        cnt=1;
    }
    void add(int a,int b,int c){
        edge[++cnt]={b,head[a],c};
        head[a]=cnt;
    }
    void adde(int a,int b,int c){
        add(a,b,c),add(b,a,0);
    }
    queue<int> q;
    bool bfs(){
        memset(dep,0,sizeof(dep));
        dep[S]=1;
        q.push(S);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=head[u];i;i=edge[i].nxt){
                int v=edge[i].to;
                if(edge[i].val&&!dep[v]){
                    dep[v]=dep[u]+1;
                    q.push(v);
                }
            }
        }
        return dep[T]>0;
    }
    int dfs(int u,int limit){
        if(u==T)return limit;
        int flow=0;
        for(int &i=head[u];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(dep[v]==dep[u]+1&&edge[i].val){
                int k=dfs(v,min(limit,edge[i].val));
                edge[i].val-=k;
                edge[i^1].val+=k;
                flow+=k;
                limit-=k;
            }
            if(!limit)break;
        }
        if(!flow)dep[u]=inf;
        return flow;
    }
    int Dinic(){
        memcpy(pre,head,sizeof(head));
        int maxflow=0;
        while(bfs()){
            maxflow+=dfs(S,inf);
            memcpy(head,pre,sizeof(head));
        }
        return maxflow;
    }
    bool vis[N];
    void dfs(int u){
        vis[u]=true;
        for(int i=head[u];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(edge[i].val&&!vis[v])dfs(v);
        }
    }
    void Plan(){
        memset(vis,false,sizeof(vis));
        dfs(S);
    }
}
int n,D;
vector<int> ans;
struct Point{
    int x,y;
    Point(int _x=0,int _y=0){x=_x,y=_y;}
    Point operator -(const Point b){
        return Point(x-b.x,y-b.y);
    }
    int operator %(const Point b){
        return x*b.y-y*b.x;
    }
}p[N];
inline int Dis(Point &a,Point &b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
inline bool Left(Point a,Point b){
    return a%b<0;
}
inline bool Para(Point a,Point b){
    return a%b==0;
}
void Solve(int a,int b){
    static int type[N];
    static vector<int> res;
    res.clear();
    int tot=0,lim=Dis(p[a],p[b]);
    Maxflow::Clear();
    Maxflow::S=a,Maxflow::T=b;
    res.push_back(a),res.push_back(b);
    for(int i=1;i<=n;++i){
        type[i]=-1;
        if(i==a||i==b)continue;
        if(Dis(p[a],p[i])>lim||Dis(p[b],p[i])>lim)continue;

        if(Para(p[i]-p[a],p[b]-p[a])){
            res.push_back(i);continue;
        }

        type[i]=Left(p[i]-p[a],p[b]-p[a]);
    }
    for(int i=1;i<=n;++i){
        if(!~type[i])continue;
        type[i]==0?Maxflow::adde(a,i,1):Maxflow::adde(i,b,1);
    }
    for(int i=1;i<=n;++i){
        if(!~type[i])continue;
        for(int j=i+1;j<=n;++j){
            if(!~type[j])continue;
            if(type[i]^type[j]){
                if(Dis(p[i],p[j])>lim){
                    type[i]==0?Maxflow::adde(i,j,1):Maxflow::adde(j,i,1);
                }
            }
        }
    }
    Maxflow::Dinic();
    Maxflow::Plan();
    for(int i=1;i<=n;++i){
        if(!~type[i])continue;
        if(type[i]^Maxflow::vis[i])res.push_back(i);
    }
    if(res.size()>ans.size()){
        ans=res;
    }
}
int main(){
    n=read(),D=read();
    for(int i=1;i<=n;++i){
        p[i].x=read(),p[i].y=read();
    }
    ans.push_back(1);
    for(int i=1;i<=n;++i){
        for(int j=i+1;j<=n;++j){
            if(Dis(p[i],p[j])<=D*D){
                Solve(i,j);
            }
        }
    }
    printf("%d\n",(int)ans.size());
    for(auto x:ans){
        printf("%d ",x);
    }
    printf("\n");
    return 0;
}