HDU 4435 charge-station （并查集）

　　先说下题目的意思：

　　　　　　在一个二维坐标系中有N个点，某人要来个走遍所有点的旅行，但是他的车每次加油后只能走M个单位距离；所以要在这个N点中选一些建立加油站；问题来了：i^th 点建加油站的花费是 2^（i-1）; 求最小话费用二进制表示；（其中1号必须建立加油站）

　　思路：有 10000>01111；所以我们可以一开始都给这些个点染色（都建立加油站），然后从高位枚举这一位可以不建立加油站么？可以的话给他去除掉；依次类推；这样就可以维护这个“最小”；

　　解法：上述思路的关键是给定一个染色方案如何判断是否合法：我的判断方法是并查集

　　　　　　　　1）根据染色分俩堆；

　　　　　　　　2）把建立加油站的点建立最小生成树,当距离大于M 时停止；

　　　　　　　　3）看建立的树是否把所有的加油点囊括在内，有不再的肯定是false；

　　　　　　　　4）没有加油站的点在暴力判断下有没有离这个点的距离小于 M/2 的加油站点；就可以了；没有就是false;

　　　　　　　　5）至此结束；

#include <cstdio>

#include <string>

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cmath>

#include <map>

using namespace std;

typedef long long LL;

struct point

{

    int x,y;

    void input()

    {

        scanf("%d%d",&x,&y);

    }

};

struct Edge

{

    int s,to;

    double dis;

    Edge(){}

    Edge(int s,int to,double dis):s(s),to(to),dis(dis){}

    bool operator < (const Edge &rht) const

    {

        return dis<rht.dis;

    }

};

point ko[129];

Edge  edge[129*129];

int DIS[129][129],fa[129], n,pos,m;

bool flag[129];

void inint(bool  t)

{

    pos=0;

    if(t)memset(flag,1,sizeof flag);

    for(int i=1;i<=128;i++)fa[i]=i;

}

int Find(int x)

{

    return x==fa[x]?x:fa[x]=Find(fa[x]);

}

double get_dis(point a,point b)

{

    int x=a.x-b.x;int y=a.y-b.y;

    return ceil(sqrt(1.0*(x*x+y*y)));

}

int Set1[129],pos1, Set2[129],pos2;

bool make()

{

    inint(false);

    pos1=pos2=0;

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

        if(flag[i])  Set1[pos1++]=i;

        else         Set2[pos2++]=i;

    for(int i=0;i<pos1;i++) for(int j=i+1;j<pos1;j++)

    {

        double dis=DIS[Set1[i]][Set1[j]];

        edge[pos++]=Edge(Set1[i],Set1[j],dis);

    }

    sort(edge,edge+pos);

    for(int i=0;i<pos;i++)

    {

        Edge & tmp=edge[i];

        if(tmp.dis>m) break;

        int x=Find(tmp.s);

        int y=Find(tmp.to);

        if(x!=y) fa[x]=y;

    }

    int FA=Find(1);

    for(int i=0;i<pos1;i++)

        if(FA!=Find(Set1[i])) return false;

    for(int i=0;i<pos2;i++)

    {

        int j=0;

        for(;j<pos1;j++)

        {

            if(DIS[Set2[i]][Set1[j]]*2.0<=m) break;

        }

        if(j==pos1) return false;

    }

    return true;

}

void solve()

{

    for(int i=n;i>=2;i--)

    {

        flag[i]=false;

        if(make()) continue;

        flag[i]=true;

    }

    int i;

    for(i=n;i>=1;i--) if(flag[i]) break;

    for(;i>=1;i--)

        printf("%d",flag[i]);

    puts("");

}

int main()

{

    while(~scanf("%d %d",&n,&m))

    {

        inint(true);

        for(int i=1;i<=n;i++)ko[i].input();

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

            DIS[i][j]=get_dis(ko[i],ko[j]);

        if(!make()){puts("-1");continue;}

        solve();

    }

    return 0;

}

巴特西

HDU 4435 charge-station （并查集）

最新文章

热门文章