加载中…
个人资料
鈞少
鈞少
  • 博客等级:
  • 博客积分:0
  • 博客访问:32,587
  • 关注人气:17
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

hdu4435 (charge-station)2012亚洲赛天津赛区E 贪心+bfs

(2012-10-27 17:01:22)
标签:

杂谈

= = !! 和队友一起做  5小时没A出来 ,  中午睡了个觉然后就想到哪出bug了

代码比较长比较臭凑合着看希望别介意

分析:首先看题意给我们的信息,每个点的加油站费用都是2的i-1次方  ,这个就给了我们一个信息 , 就是宁愿在比他小的地方都建加油站也好过在大的点建(当然要符合都能浏览一遍的条件) , 那么就很容易的看出这是一个贪心 , 先想如果n个点都有加油站那么在距离满足的情况下都能观光一遍 , 再看 点只有128个, 那么我们可以放心的先全部建加油站 , 然后在从n开始往下选取加油站删除 , 枚举每个点 , 删除后做一次bfs ,如果不能完成观光那么我们就把加油站恢复 。
bfs的时候我们先要确保每个加油站在d距离都可以到达 , 然后我们我们在搜索一次没加油站的点 , 没加油站的点如果能到达的话肯定是在某加油站的d/2的距离 , 要返回时否则无法返回~

#include <iostream>
#include <string>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>

using namespace std;

#define eps 1e-8

typedef struct
{
    double x,y;
}element;

element node[200];
int n,d;
int cost[200][200];
int edge[200][200];
bool vis[200];
bool oil[200];
int tempv = 0 ;
queue<int > q,que;

inline int node_dis(element node1 , element node2)
{
    return (int)ceil(sqrt((node1.x - node2.x)*(node1.x - node2.x) + (node1.y - node2.y)*(node1.y - node2.y)));
}

inline void cal_dis()
{
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = i + 1 ; j <= n  ; ++j)
        {
            edge[i][j] = edge[j][i] = cost[i][j] = cost[j][i] = node_dis(node[i] , node[j]);
        }
        edge[i][i] = cost[i][i] = 0;
    }
}


void bfs()
{
    q.push(1) , que.push(1);
    vis[1] = 1;
    tempv = 1;
    while(!q.empty())
    {
        
        int idx = q.front();
        q.pop();
        
        for(int i = 2 ; i <= n ; ++i)
        {
            if(vis[i])continue; 
            if(!oil[i] && cost[idx][i] <= d)// 0 有  1无   
            {
                q.push(i);
                que.push(i);
                vis[i] = 1;
                tempv++;
            }
            
        }
        
    }
    
    while(!que.empty())
    {
        int idx = que.front();
        que.pop();
        
        for(int i = 2 ; i <= n ; ++i)//搜索可否达到加油站 
        {
            if(vis[i])continue; 
            if( cost[idx][i] <= d/2 )// 0 有  1无   
            {
                vis[i] = 1;
                tempv++;
            }
            
        }
        
        
    }
        
}

int main()
{
    while(~scanf("%d%d",&n,&d))
    {
        memset(vis , 0 , sizeof(vis));
        memset(oil , 0 , sizeof(oil));// 0 有  1无  
        //oil[1] = 1;
        for(int i = 1 ; i <= n ; ++i)
        {
            scanf("%lf%lf",&node[i].x , &node[i].y);
        }
        
        cal_dis();//统计每两点的距离 ceil(sqrt((xi - xj)2 + (yi - yj)2)).
        
        
        //先判断都建加油站能不能参观完  不能-1 
        tempv = 0 ;
        bfs();
        bool tmp  = 0;
        if(tempv != n)
        {
            puts("-1");
            continue;
        }
        
        int ans = 0;
        
        for(int i = n ; i >= 2 ; --i)
        {
            tempv = 0 ;
            memset(vis , 0 , sizeof(vis));
            oil[i] = 1; 
            bfs();
            if(tempv != n)
                oil[i] = 0;
        }
        int ppp = 0;
        for(int i = n ; i >= 1 ; --i)
        {
            if(!ppp && oil[i] == 1)continue;
            if(!oil[i]) 
                printf("1");
            else
                printf("0");
            ppp++;
        }
        cout<<endl;
        
    }
    
    return 0;
}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有