(中等) HDU 5046 Airport ，DLX+可重复覆盖+二分。

　　Description

　　The country of jiuye composed by N cites. Each city can be viewed as a point in a two- dimensional plane with integer coordinates (x,y). The distance between city i and city j is defined by d  = |x  - x | + |y  - y |. jiuye want to setup airport in K cities among N cities. So he need your help to choose these K cities, to minimize the maximum distance to the nearest airport of each city. That is , if we define d (1 ≤ i ≤ N ) as the distance from city i to the nearest city with airport. Your aim is to minimize the value max{d |1 ≤ i ≤ N }. You just output the minimum.

 

　　题目是最大值最小化，明显的二分，然后对于每一个值，判断能不能找到K个以内的来覆盖。。。。。。

 

　　做的时候要注意二分的问题，还有就是要用long long 别用int，还有就是abs。。。不知道怎么回事被坑了，自己写了一个abs来用的。。。。。。

 

#include<iostream>

#include<cstring>

#include<utility>

#include<algorithm>

using namespace std;

const int MaxN=;

const int MaxM=;

const int MaxNode=MaxN*MaxM;

int N,K;

long long X[],Y[];

long long abs1(long long x)

{

    if(x<)

        x=-x;

    return x;

}

struct DLX

{

    int U[MaxNode],D[MaxNode],L[MaxNode],R[MaxNode],col[MaxNode];

    int S[MaxM],H[MaxN];

    int size,m,n;

    void init(int _n,int _m)

    {

        n=_n;

        m=_m;

        size=m;

        for(int i=;i<=m;++i)

        {

            U[i]=D[i]=i;

            L[i]=i-;

            R[i]=i+;

            S[i]=;

        }

        L[]=m;

        R[m]=;

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

            H[i]=-;

    }

    void Link(int r,int c)

    {

        col[++size]=c;

        ++S[c];

        U[size]=U[c];

        D[size]=c;

        D[U[c]]=size;

        U[c]=size;

        if(H[r]==-)

            H[r]=L[size]=R[size]=size;

        else

        {

            L[size]=L[H[r]];

            R[size]=H[r];

            R[L[H[r]]]=size;

            L[H[r]]=size;

        }

    }

    void remove(int c)

    {

        for(int i=D[c];i!=c;i=D[i])

        {

            L[R[i]]=L[i];

            R[L[i]]=R[i];

        }

    }

    void resume(int c)

    {

        for(int i=U[c];i!=c;i=U[i])

            L[R[i]]=R[L[i]]=i;

    }

    bool vis[MaxM];

    int getH()

    {

        int ret=;

        for(int i=R[];i;i=R[i])

            vis[i]=;

        for(int c=R[];c;c=R[c])

            if(vis[c])

            {

                ++ret;

                vis[c]=;

                for(int i=D[c];i!=c;i=D[i])

                    for(int j=R[i];j!=i;j=R[j])

                        vis[col[j]]=;

            }

        return ret;

    }

    bool Dance(int d)

    {

        if(d+getH()>K)

            return ;

        if(R[]==)

            return d<=K;

        int c=R[];

        for(int i=R[];i;i=R[i])

            if(S[i]<S[c])

                c=i;

        for(int i=D[c];i!=c;i=D[i])

        {

            remove(i);

            for(int j=R[i];j!=i;j=R[j])

                remove(j);

            if(Dance(d+))

                return ;

            for(int j=L[i];j!=i;j=L[j])

                resume(j);

            resume(i);

        }

        return ;

    }

};

pair <long long,int> rem[][];

long long remP[];

DLX dlx;

void slove(long long maxNum)

{

    long long L=,R=maxNum,M,ans;

    for(int i=;i<=N;++i)

    {

        for(int j=;j<=N;++j)

        {

            rem[i][j].first=(long long)abs1(X[i]-X[j])+(long long)abs1(Y[i]-Y[j]);

            rem[i][j].second=j;

        }

        sort(rem[i]+,rem[i]+N+);

        remP[i]=;

    }

/*    dlx.init(N,N);

    for(M=L;M<=R;++M)

    {

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

            while(rem[i][remP[i]].first<=M)

            {

                dlx.Link(i,rem[i][remP[i]].second);

                ++remP[i];

            }

        if(dlx.Dance(0))

            break;

    }*/

    while(R>L)

    {

        M=(L+R)/;

        dlx.init(N,N);

        for(int i=;i<=N;++i)

            for(int j=;j<=N;++j)

                if(rem[i][j].first<=M)

                    dlx.Link(i,rem[i][j].second);

                else

                    break;

        if(dlx.Dance())

            R=M;

        else

            L=M+;

    }

    cout<<L<<endl;

}

int main()

{

    ios::sync_with_stdio(false);

    int T;

    long long maxX,maxY,minX,minY;

    cin>>T;

    for(int cas=;cas<=T;++cas)

    {

        cin>>N>>K;

        cin>>X[]>>Y[];

        maxX=minX=X[];

        maxY=minY=Y[];

        for(int i=;i<=N;++i)

        {

            cin>>X[i]>>Y[i];

            if(maxX<X[i])

                maxX=X[i];

            if(maxY<Y[i])

                maxY=Y[i];

            if(minX>X[i])

                minX=X[i];

            if(minY>Y[i])

                minY=Y[i];

        }

        cout<<"Case #"<<cas<<": ";

        slove(maxX+maxY-minX-minY);

    }

    return ;

}