POJ - 3662 Telephone Lines （dijstra+二分）

题意：有N个独立点，其中有P对可用电缆相连的点，要使点1与点N连通，在K条电缆免费的情况下，问剩下的电缆中，长度最大的电缆可能的最小值为多少。

分析：

1、二分临界线（符合的情况的点在右边），找可能的最小值，假设为mid。

2、将大于mid的边变为1，小于等于mid的边变为0（表示这些边由自己承包），由此算出1~N的最短路长度为x。x即为所用的大于mid的电缆个数。

3、若x<=K,则符合情况，但是想让所用的免费电缆条数x更多，所以让mid更小一些，这样自己承包的边也减少，x将更大，即r = mid;

4、若x>K，则所用免费电缆条数x超过了K条，不再符合题意，自己承包的边过少了，所以l = mid + 1;

#pragma comment(linker, "/STACK:102400000, 102400000")

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define Min(a, b) ((a < b) ? a : b)

#define Max(a, b) ((a < b) ? b : a)

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 1000 + 10;

const int MAXT = 10000 + 10;

using namespace std;

int N, P, K;

struct Edge{

    int from, to, dist;

    Edge(int f, int t, int d):from(f), to(t), dist(d){}

};

struct HeapNode{

    int d, u;

    HeapNode(int dd, int uu):d(dd), u(uu){}

    bool operator < (const HeapNode& rhs)const{

        return d > rhs.d;

    }

};

struct Dijkstra{

    int n, m;

    vector<Edge> edges;

    vector<int> G[MAXN];

    bool done[MAXN];

    int d[MAXN];

    int p[MAXN];

    void init(int n){

        this -> n = n;

        for(int i = 0; i < n; ++i) G[i].clear();

        edges.clear();

    }

    void AddEdge(int from, int to, int dist){

        edges.push_back(Edge(from, to, dist));

        m = edges.size();

        G[from].push_back(m - 1);

    }

    void dijkstra(int s, int t){

        priority_queue<HeapNode> Q;

        for(int i = 0; i < N; ++i) d[i] = INT_INF;

        d[s] = 0;

        memset(done, 0, sizeof done);

        Q.push(HeapNode(0, s));

        while(!Q.empty()){

            HeapNode x = Q.top();

            Q.pop();

            int u = x.u;

            if(done[u]) continue;

            done[u] = true;

            for(int i = 0; i < G[u].size(); ++i){

                Edge& e = edges[G[u][i]];

                int tmp = e.dist > t ? 1 : 0;

                if(d[e.to] > d[u] + tmp){

                    d[e.to] = d[u] + tmp;

                    p[e.to] = G[u][i];

                    Q.push(HeapNode(d[e.to], e.to));

                }

            }

        }

    }

}dij;

bool judge(int x){

    dij.dijkstra(0, x);

    if(dij.d[N - 1] <= K) return true;

    return false;

}

int solve(){

    int l = 0, r = 1e6;

    while(l < r){

        int mid = l + (r - l) / 2;

        if(judge(mid)) r = mid;

        else l = mid + 1;

    }

    if(judge(r)) return r;

    return -1;

}

int main(){

    dij.init(N);

    scanf("%d%d%d", &N, &P, &K);

    for(int i = 0; i < P; ++i){

        int a, b, l;

        scanf("%d%d%d", &a, &b, &l);

        dij.AddEdge(a - 1, b - 1, l);

        dij.AddEdge(b - 1, a - 1, l);

    }

    printf("%d\n", solve());

    return 0;

}

巴特西

POJ - 3662 Telephone Lines （dijstra+二分）

最新文章

热门文章