TopCoder SRM 642 Div.2 1000 --二分+BFS

题意：给你一张图，N个点(0~N-1),m条边，国王要从0到N-1，国王携带一个值，当走到一条边权大于此值的边时，要么不走，要么提升该边的边权，提升k个单位花费k^2块钱，国王就带了B块钱，问能携带的最大值是多少。

解法: 二分此值，然后BFS跑遍每个点，记录到达每个点的最小花费Mincost，如果Mincost[N-1] <= B,则此值可行，往上再二分，否则往下二分。

比赛时候本来我的二分方法应该返回high的，结果返回low，怎么都过不了样例，比赛完才发现此处的问题。真是太弱。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#define ll long long

using namespace std;

struct node

{

    int u;

    long long cost;

};

class TallShoes

{

public:

    long long mp[][],Mincost[];

    int N;

    bool bfs(int N,int S,int E,long long hei,long long B)

    {

        int i;

        Mincost[] = ;

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

            Mincost[i] = 10000000000000000LL;

        queue<node> que;

        node now;

        now.u = S;

        now.cost = ;

        que.push(now);

        while(!que.empty())

        {

            node tmp = que.front();

            que.pop();

            int u = tmp.u;

            long long cost = tmp.cost;

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

            {

                if(u == i) continue;

                if(mp[u][i] >= 10000000000000000LL) continue;

                if(mp[u][i] >= hei)

                {

                    if(Mincost[i] > cost)

                    {

                        Mincost[i] = cost;

                        now.u = i, now.cost = Mincost[i];

                        que.push(now);

                    }

                }

                else

                {

                    long long dif = hei-mp[u][i];

                    if(Mincost[i] > cost + dif*dif)

                    {

                        Mincost[i] = cost + dif*dif;

                        now.u = i, now.cost = Mincost[i];

                        que.push(now);

                    }

                }

            }

        }

        if(Mincost[E] <= B) return true;

        return false;

    }

    int maxHeight(int N, vector <int> X, vector <int> Y, vector <int> height, long long B)

    {

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

        {

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

                mp[i][j] = 10000000000000000LL;

            mp[i][i] = ;

        }

        for(int i=;i<X.size();i++)

            mp[X[i]][Y[i]] = mp[Y[i]][X[i]] = height[i];

        long long low = , high = 1000000000LL;

        while(low <= high)

        {

            long long mid = (low+high)/2LL;

            if(bfs(N,,N-,mid,B)) low = mid+;

            else                   high = mid-;

        }

        return high;

    }

};

巴特西

TopCoder SRM 642 Div.2 1000 --二分+BFS

最新文章

热门文章