题解：Telephone Lines（P3662）

一、题目分析

本题要求将农场（节点N）通过电话线路连接到电话系统（节点1），并最小化需要付费的最长电缆长度。关键条件：

• 共有N个电线杆（节点），P条可用电缆（边）
• 电话公司免费提供K条电缆，剩余电缆中最长的需付费
• 若无法连接，输出-1；若无需付费，输出0

二、解题思路

1. 二分答案转化问题：
   二分枚举可能的最长电缆长度$L$，判断是否存在一条路径，使得长度超过$L$的边不超过$K$条。

2. 0-1 BFS优化：
   将边权重新定义为：

   • 若边长度$>L$，边权为1（需付费）
   • 若边长度$\leq L$，边权为0（免费）
     使用Dijkstra算法计算从1到N的最短路径（即最少的付费边数）。

3. 可行性判断：
   若最短路径长度$\leq K$，说明存在一条路径使得付费边数不超过$K$，此时$L$是可行解，尝试更小的$L$；否则尝试更大的$L$。

三、代码解析

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=1010;
const int INF=999999999;
int map[maxn][maxn];  // 邻接矩阵存储边权
struct edge {
    int u, v, l;
};
struct edge E[maxn*10];  // 存储所有边

bool cmp(edge a, edge b) {
    return a.l < b.l;
}

// 构建邻接矩阵：长度>l的边权为1，否则为0
void build(int n, int p, int l) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            map[i][j] = INF;
        }
    }
    for(int i=0; i<p; i++) {
        int a = E[i].u, b = E[i].v, c = E[i].l;
        if(c > l)
            map[a][b] = map[b][a] = 1;
        else
            map[a][b] = map[b][a] = 0;
    }
}

// Dijkstra算法计算从s到n的最短路径
int Dijkstra(int s, int n) {
    bool vis[maxn];
    int dis[maxn];
    for(int i=1; i<=n; i++) {
        dis[i] = (s==i ? 0 : map[s][i]);
        vis[i] = false;
    }
    vis[s] = true;
    dis[s] = 0;
    
    for(int i=1; i<n; i++) {
        int t = INF, k = -1;
        for(int j=1; j<=n; j++) {
            if(!vis[j] && dis[j] < t) {
                t = dis[j];
                k = j;
            }
        }
        if(t == INF) break;
        vis[k] = true;
        
        for(int j=1; j<=n; j++) {
            if(!vis[j] && dis[j] > dis[k] + map[k][j]) {
                dis[j] = dis[k] + map[k][j];
            }
        }
    }
    return dis[n];
}

// 二分查找最小的L
int bfind(int p, int n, int k) {
    int l = 0, r = p-1;
    while(l <= r) {
        int m = (l + r) / 2;
        build(n, p, E[m].l);
        if(Dijkstra(1, n) <= k)  // 付费边数不超过k，尝试更小的L
            r = m - 1;
        else
            l = m + 1;
    }
    return l;
}

int main() {
    int n, p, k;
    while(scanf("%d %d %d", &n, &p, &k) != EOF) {
        for(int i=0; i<p; i++)
            scanf("%d %d %d", &E[i].u, &E[i].v, &E[i].l);
        sort(E, E+p, cmp);  // 按边权排序
        
        build(n, p, 0);
        int ans = Dijkstra(1, n);
        if(ans == INF)  // 无法到达
            printf("%d\n", -1);
        else {
            if(ans <= k)  // 无需付费
                printf("%d\n", 0);
            else {
                int indx = bfind(p, n, k);
                printf("%d\n", E[indx].l);
            }
        }
    }
    return 0;
}

四、关键步骤解析

1. 边权重构
   $build$函数将原始边权转换为0-1边权：

   • 若边长度$>L$，边权为1（需付费）
   • 若边长度$\leq L$，边权为0（免费）

2. Dijkstra算法
   计算从节点1到N的最短路径，其中路径长度表示付费边的数量。若最短路径长度$\leq K$，则$L$是可行解。

3. 二分查找
   在排序后的边权数组中二分查找最小的$L$，使得存在一条路径的付费边数$\leq K$。

五、示例解析

对于输入：

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. 边权排序：
   边权按升序排列为：3, 4, 5, 6, 7, 8, 9。

2. 二分查找：

   • 初始$L=\frac{0+6}{2}=3$，构建图后Dijkstra计算得最短路径长度为2（需2条付费边），2>1，$L$太小，更新$l=4$。
   • $L=4$，最短路径长度为1（需1条付费边），1≤1，$L$可行，更新$r=3$。
   • 最终$L=4$为最小可行解。

六、注意事项

1. 预处理判断连通性
   初始时检查是否存在从1到N的路径，若不存在直接输出-1。

2. 二分边界处理
   二分查找的上下界需合理设置，确保覆盖所有可能的边权值。

3. Dijkstra算法适用性
   本题使用标准Dijkstra算法即可，因边权仅为0和1，若追求更高效率，可使用双端队列BFS优化。

七、复杂度分析

• 时间复杂度：$O(P \log P + P \log P \cdot N^2)$
  排序边权$O(P \log P)$，二分查找$O(\log P)$，每次Dijkstra$O(N^2)$。
• 空间复杂度：$O(N^2 + P)$
  邻接矩阵存储图，边数组存储所有边。

八、优化方向

1. 邻接表代替邻接矩阵
   对于稀疏图，使用邻接表可将Dijkstra时间复杂度优化至$O((N+P)\log N)$。

2. 0-1 BFS
   由于边权仅为0和1，使用双端队列BFS可将单次路径计算优化至$O(N+P)$。