程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4435 charge-station(暴力+判圖)

HDU 4435 charge-station(暴力+判圖)

編輯：C++入門知識

HDU 4435 charge-station(暴力+判圖)

題目大意：給你一些點，他們可以連通，如果距離超過了d那麼就要經過加油站，建立加油站的費用為第i個點是2^(i-1)。求費用最小，輸出二進制表示的最小費用。

費用和sum最壞等於=2^0+2^1+……+2^(n-1)。所以最高位為0這個數字才會最小，從最高位暴力枚舉如果刪掉這個點之後圖是連通的那麼就可以刪掉，否則不可以。

求圖是否連通的時候可以爆搜求解，也可以並查集。

charge-station

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1053 Accepted Submission(s): 554

Problem Description There are n cities in M^3's empire. M^3 owns a palace and a car and the palace resides in city 1. One day, she wants to travel around all the cities from her palace and finally back to her home. However, her car has limited energy and can only travel by no more than D meters. Before it was run out of energy, it should be charged in some oil station. Under M^3's despotic power, the judge is forced to build several oil stations in some of the cities. The judge must build an oil station in city 1 and building other oil stations is up to his choice as long as M^3 can successfully travel around all the cities.
Building an oil station in city i will cost 2^i-1 MMMB. Please help the judge calculate out the minimum cost to build the oil stations in order to fulfill M^3's will.

Input There are several test cases (no more than 50), each case begin with two integer N, D (the number of cities and the maximum distance the car can run after charged, 0 < N ≤ 128).
Then follows N lines and line i will contain two numbers x, y(0 ≤ x, y ≤ 1000), indicating the coordinate of city i.
The distance between city i and city j will be ceil(sqrt((xi - xj)² + (yi - yj)²)). (ceil means rounding the number up, e.g. ceil(4.1) = 5)

Output For each case, output the minimum cost to build the oil stations in the binary form without leading zeros.
If it's impossible to visit all the cities even after all oil stations are build, output -1 instead.

Sample Input

Sample Output

11
111
-1
10111011
Hint
In case 1, the judge should select (0, 0) and (0, 3) as the oil station which result in the visiting route: 1->3->2->3->1. And the cost is 2^(1-1) + 2^(2-1) = 3.

Source 2012 Asia Tianjin Regional Contest

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define eps 1e-8
///#define LL long long
#define LL __int64
#define INF 0x3f3f3f
#define PI 3.1415926535898
#define mod 1000000007


using namespace std;

const int maxn = 210;

bool vis[maxn];
int mp[maxn][maxn];

struct node
{
    int x, y;
} f[maxn];

int n, d;

double Dis(int a, int b)
{
    return sqrt(((f[a].x-f[b].x)*(f[a].x-f[b].x) + (f[a].y-f[b].y)*(f[a].y-f[b].y))*1.0);
}

bool bfs()
{
    bool flag[maxn];
    int dis[maxn];
    memset(flag, false, sizeof(flag));
    for(int i = 1; i <= n; i++)
    {
        if(vis[i])
        {
            dis[i] = 0;
            continue;
        }
        dis[i] = INF;
    }
    queue que;
    que.push(1);
    flag[1] = true;
    while(!que.empty())
    {
        int x = que.front();
        que.pop();
        for(int i = 1; i <= n; i++)
        {
            if(flag[i] || mp[x][i] > d) continue;
            dis[i] = min(dis[i], dis[x]+mp[x][i]);
            if(vis[i])
            {
                flag[i] = true;
                que.push(i);
            }
        }
    }
    for(int i = 1; i <= n; i++)
    {
        if(vis[i] && !flag[i]) return false;
        if(!vis[i] && 2*dis[i] > d) return false;
    }
    return true;
}

int main()
{
    while(~scanf("%d %d",&n, &d))
    {
        for(int i = 1; i <= n; i++) scanf("%d %d",&f[i].x, &f[i].y);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                mp[i][j] = ceil(Dis(i, j));
        for(int i = 1; i <= n; i++) vis[i] = true;
        if(!bfs())
        {
            cout<<-1<= 1; i--)
        {
            vis[i] = false;
            if(!bfs()) vis[i] = true;
        }
        int x = n;
        while(!vis[x]) x--;
        for(int i = x; i >= 1; i--) cout<