首页 > 代码库 > HDU 4435 charge-station (并查集)

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 (并查集)