POJ-Telephone Lines

题目描述：

Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system.

There are N (1 ≤ N ≤ 1,000) forlorn telephone poles conveniently numbered 1..N that are scattered around Farmer John’s property; no cables connect any them. A total of P (1 ≤ P ≤ 10,000) pairs of poles can be connected by a cable; the rest are too far apart.

The i-th cable can connect the two distinct poles Ai and Bi, with length Li (1 ≤ Li ≤ 1,000,000) units if used. The input data set never names any {Ai, Bi} pair more than once. Pole 1 is already connected to the phone system, and pole N is at the farm. Poles 1 and N need to be connected by a path of cables; the rest of the poles might be used or might not be used.

As it turns out, the phone company is willing to provide Farmer John with K (0 ≤ K < N) lengths of cable for free. Beyond that he will have to pay a price equal to the length of the longest remaining cable he requires (each pair of poles is connected with a separate cable), or 0 if he does not need any additional cables.

Determine the minimum amount that Farmer John must pay.

输入：

  • Line 1: Three space-separated integers: N, P, and K
  • Lines 2..P+1: Line i+1 contains the three space-separated integers: Ai, Bi, and Li

输出：

  • Line 1: A single integer, the minimum amount Farmer John can pay. If it is impossible to connect the farm to the phone company, print -1.

输入示例：

1
2
3
4
5
6
7
8
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

输出示例：

1
4

题目大意：

一电话公司要链接编号1和N的电话，中间可能需要架设多条电话线，线缆厂商可以免费给电话公司铺设k条电缆，超过k条之后，要按其余的线缆中最长的进行相应收费费用与长度相同，求电话公司需要付的最小费用。

思路：

其实就是求无向图中，从1到N中，使最多可以“宽恕”k条最长边之后最长的边的长度尽可能小的路径。

单独求这样一个问题好像很复杂，我们稍加分析发现，答案一定在给定的边长、零或者不存在这样的路径这三种情况中，我们先假定一个答案，用这个答案去试探从1-N的路径有没有符合条件的。

具体的判断就是求一条大于答案的边长数最小的一条路径。可以使用最短路来求，松弛条件根据到当前边的超过答案的数量中选择更小的一条边。我们最后判断到达N后其数量是否超过k，就能判断这是否是一条符合条件的边。

然后将存放所有可能是答案的数组排序后进行二分。

这里求“最短路”用了两个最短路模板：

Solution1（Dijkstra）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*
 * @Date: 2019-10-07 18:55:30
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-10-08 22:59:49
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MAXN = 10000+10;
const int INF = 0x3f3f3f3f;
int n,p,k;
struct node{
    int b,ca;
    node(int _b,int _ca):b(_b),ca(_ca){}
    node(){}
    bool operator<(const node &q)const{
        return ca > q.ca;
    }
};
vector<node> V[MAXN];
int dis[MAXN]; //dis存超过目标值x的电话线条数。
int vis[MAXN];
int cost[MAXN];
int Dijkstra(int x){
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1] = 0;
    priority_queue<node> q;
    q.push(node(1,dis[1]));
    node temp;
    while(!q.empty()){
        temp = q.top(); q.pop();
        int u = temp.b;
        if(vis[u])continue;
        vis[u] = 1;
        for(int i = 0; i < V[u].size(); i++){
            int v = V[u][i].b;
            int c = V[u][i].ca;
            c = c > x ? 1 : 0;
            //更新到当前结点的超过x的条数
            if(!vis[v] && dis[v] > dis[u] + c){
                
                dis[v] = dis[u] + c;
                q.push(node(v,dis[v]));
            }
        }
    }
    //是
    return dis[n]<= k;
}




int main(){
    freopen("in.txt","r",stdin);
    scanf("%d%d%d",&n,&p,&k);
    for(int i = 0; i < p; i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        V[a].push_back(node(b,c));
        V[b].push_back(node(a,c));
        cost[i+1] = c; 
    }
    //按长度进行二分，根据超过该长度的个数是否超过k来确定边界。
    sort(cost+1,cost+1+p);
    if(!Dijkstra(cost[p])){
        printf("-1\\n");
        return 0;
    }
    //答案有可能是0，所以从0开始。
    int l = 0, r = p-1;
    while(l < r){
        int mid = l+r>>1;
        if(Dijkstra(cost[mid])) r = mid;
        else l = mid+1;
    }
    printf("%d",cost[l]);
    return 0;
}

Solution2（SPFA）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/*
 * @Date: 2019-10-07 18:55:30
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-10-09 19:32:17
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MAXN = 10000+10;
const int INF = 0x3f3f3f3f;
int n,p,k;
struct node{
    int b,ca;
    node(int _b,int _ca):b(_b),ca(_ca){}
    node(){}
    bool operator<(const node &q)const{
        return ca > q.ca;
    }
};
vector<node> V[MAXN];
int dis[MAXN]; //dis存超过目标值x的电话线条数。
int vis[MAXN];
int inq[MAXN];
int cost[MAXN];
int SPFA(int x){
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(inq,0,sizeof(inq));
    
    dis[1] = 0;
    queue<int> q;
    q.push(1);
    node temp;
    inq[1] = 1;
    while(!q.empty()){
        int u = q.front(); q.pop();
        inq[u] = false;
        for(int i = 0; i < V[u].size(); i++){
            int v = V[u][i].b;
            int c = V[u][i].ca;
            c = c > x ? 1 : 0;
            //更新到当前结点的超过x的条数
            if(dis[v] > dis[u] + c){
                
                dis[v] = dis[u] + c;
                if(!inq[v]){
                    q.push(v);
                    inq[v] = 1;
                }
            }
        }
    }
    //是
    return dis[n]<= k;
}




int main(){
    freopen("in.txt","r",stdin);
    scanf("%d%d%d",&n,&p,&k);
    for(int i = 0; i < p; i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        V[a].push_back(node(b,c));
        V[b].push_back(node(a,c));
        cost[i+1] = c; 
    }
    //按长度进行二分，根据超过该长度的个数是否超过k来确定边界。
    sort(cost+1,cost+1+p);
    if(!SPFA(cost[p])){
        printf("-1\\n");
        return 0;
    }
    //答案有可能是0，所以从0开始。
    int l = 0, r = p-1;
    while(l < r){
        int mid = l+r>>1;
        if(SPFA(cost[mid])) r = mid;
        else l = mid+1;
    }
    printf("%d",cost[l]);
    return 0;
}