题解 P1948 【[USACO08JAN]电话线Telephone Lines】

· · 题解

本题作法 ： 二分答案+双端队列bfs

前序知识点：图的储存与遍历，二分答案，bfs求最短路

在做这道题之前，可以看一下 p2243 电路维修，注意到转化为一个边权只为 0 或 1 的无向图。

因此，我们可以二分最大的花费x，x属于[l,r],(l为最小花费，r为最大花费)， x然后将大于x的边看做权值为1的边，将小于等于x的边看做权值为零的边，然后找到从点1到点n的最短路，若最短路的长度大于k，则要连接的对数大于k对，在[x+1,r]中继续二份查找；若最短路的长度小于k，则要连接的对数比k小，在[l,x]中继续二份查找，最终，l即为所求。

贴上ac代码

#include <iostream>
#include <algorithm>
#include <deque>
#include <cstring>

using namespace std;

int vis[10008];
int d[10008];
int head[10008], edge[100008], ver[100008], next[100008];
int tot;
int n, p, k, maxx = 0;
void add(int x, int y, int z) //邻接表建图，注意无向
{
    ver[++tot] = y;
    edge[tot] = z;
    next[tot] = head[x];
    head[x] = tot;
    ver[++tot] = x;
    edge[tot] = z;
    next[tot] = head[y];
    head[y] = tot;
}
int check(int x) //二分检测
{
//  cout<<x<<":";
    //双端bfs，参考p2243
    memset(d,0,sizeof(d));
    memset(vis,0,sizeof(vis));
    deque<int> q;
    q.push_back(1);
    d[1] = 0;
    vis[1] = 1;
    while(q.size())
    {
        int a = q.front();
        q.pop_front();
        for(int i = head[a]; i; i = next[i])
        {
            int y = ver[i];
            if(!vis[y] || d[y] >= d[a] + 1)
            if(edge[i] <= x)
            {
                vis[y] = 1;
                q.push_front(y);
                d[y] = d[a];
            //  cout<<"d"<<y<<"="<<d[a]<<endl;
            }
            else 
            {
                vis[y] = 1;
                q.push_back(y);
                d[y] = d[a] + 1; 
            //  cout<<"d"<<y<<"="<<d[a]+1<<endl;
            }
        }
    }
    //cout<<d[n]<<endl;
    if(d[n] > k)
    return 0;
    else
    return 1;
}
int main()
{
    cin>>n>>p>>k;
    for(int i = 0; i < p; i++)
    {
        int x, y, z;
        cin>>x>>y>>z;
        add(x, y, z);
        maxx = max(maxx, z);
    } 
//  cout<<maxx<<endl;
    int l = 1, r = maxx;
    while(l < r)
    {
        int mid = (l + r) / 2;
        if(check(mid))
        r  = mid;
        else
        l = mid + 1;
     } 
     if(l!=1) 
     cout<<l;
     else
     cout<<"-1";
    return 0;
}

注意几点：

  1. 最后答案需特判，若不满足，输出-1；
  2. 请注意这一行
    if(!vis[y] || d[y] >= d[a] + 1)

    可结合样例的图示，尝试理解；