问题描述

FJ的农场周围分布着N(1<=N<=1,000)根按1..N顺次编号的废弃的电话线杆,任意两根电话线杆间都没有电话线相连。一共P(1<=P<=10,000)对电话线杆间可以拉电话线。第i对电话线杆的两个端点分别为A_i、B_i,它们间的距离为L_i(1<=L_i<=1,000,000)。数据中保证每对{A_i,B_i}最多只出现1次。
FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径,其余的电话线杆并不一定要连入电话网络。经过谈判,电信公司最终同意免费为FJ连结K(0<=K<N)对由FJ指定的电话线杆。对于此外的那些电话线,FJ需要为它们付的费用,等于其中最长的电话线的长度(每根电话线仅连结一对电话线杆)。如果需要连结的电话线杆不超过K对,那么FJ的总支出为0。
请你计算一下,FJ最少需要在电话线上花多少钱。

输入

第1行: 3个用空格隔开的整数:N,P,以及K
第2..P+1行: 第i+1行为3个用空格隔开的整数:A_i,B_i,L_i

输出

第1行: 输出1个整数,为FJ在这项工程上的最小支出。
如果任务不可能完成, 输出-1

思路

一般求“最大的最小值”或“最小的最大值”都很容易想到二分。这道题求的是第K+1大的最小值,所以也同样可以使用二分。

我们二分答案,设当前二分的答案为x。此时最大的边权<=x,显然当边的权值大于x时,这条边就应该免费。判断此时是否符合要求就只需要判断到达n节点时经过免费的边数是否大于k。

我们可以用SPFA来处理到达n节点时经过最少的免费边数。如果一条边的权值大于x,就设它的距离为1,否则为0。如果到n点的距离<=k,就是符合要求的。

代码

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define MAXN 1005
#define MAXE 10005
using namespace std;

struct Edge {int next, to, dis;} edge[MAXE*2];

int n, m, k, a, b, c, cnt, ans=-1, dis[MAXN], head[MAXN];
bool vis[MAXN];

void addedge(int from, int to, int dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

bool check(int lim)
{
    queue<int> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    vis[1]=true; dis[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        vis[x]=false;
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            int d=(edge[i].dis>lim);
            if(dis[x]+d<dis[to])
            {
                dis[to]=dis[x]+d;
                if(vis[to]) continue;
                vis[to]=true;
                q.push(to);
            }
        }
    }
    return dis[n]<=k;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        addedge(a, b, c);
        addedge(b, a, c);
    }
    int l=0, r=1000000;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))  ans=mid, r=mid-1;
        else l=mid+1;
    }
    printf("%d\n", ans);
} 

1 对 “BZOJ1614 Telephone Lines [SPFA+二分]”的想法;

发表评论

邮箱地址不会被公开。 必填项已用*标注