BZOJ 1614: [Usaco2007 Jan]Telephone Lines架设电话线 (二分+spfa)

Posted by 111qqz on Sunday, May 22, 2016

TOC

1614: [Usaco2007 Jan]Telephone Lines架设电话线

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1325  Solved: 570
[Submit][Status][Discuss]

Description

Farmer John打算将电话线引到自己的农场,但电信公司并不打算为他提供免费服务。于是,FJ必须为此向电信公司支付一定的费用。 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次。编号为1的电话线杆已经接入了全国的电话网络,整个农场的电话线全都连到了编号为N的电话线杆上。也就是说,FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径,其余的电话线杆并不一定要连入电话网络。 经过谈判,电信公司最终同意免费为FJ连结K(0 <= K < N)对由FJ指定的电话线杆。对于此外的那些电话线,FJ需要为它们付的费用,等于其中最长的电话线的长度(每根电话线仅连结一对电话线杆)。如果需要连结的电话线杆不超过 K对,那么FJ的总支出为0。 请你计算一下,FJ最少需要在电话线上花多少钱。

Input

  • 第1行: 3个用空格隔开的整数:N,P,以及K

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

Output

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

Sample Input

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

输入说明:

一共有5根废弃的电话线杆。电话线杆1不能直接与电话线杆4、5相连。电话
线杆5不能直接与电话线杆1、3相连。其余所有电话线杆间均可拉电话线。电信
公司可以免费为FJ连结一对电话线杆。

Sample Output

4

输出说明:

FJ选择如下的连结方案:1->3;3->2;2->5,这3对电话线杆间需要的
电话线的长度分别为4、3、9。FJ让电信公司提供那条长度为9的电话线,于是,
他所需要购买的电话线的最大长度为4。

HINT

思路:一开始把电话线条数和长度分别作为第一第二关键字,然后spfa.然后记录路径,找k个最大的以后的中最长的电话线就是答案。发现样例就是反例。。智力-2.

正确的做法是二分电话线的最大长度,大于最大长度的电话线交给电信公司取搞,看交给电信公司搞的电话线数目是否小于等于k.

二分的功夫还是不到家呀。。想不到。。
不过这道题和那个中国印度被喜马拉雅山脉阻隔,二分+bfs判断连通性的题目有点类似呢。

/* ***********************************************
Author :111qqz
Created Time :2016年04月02日 星期六 17时50分13秒
File Name :code/bzoj/1614.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E3+7;
int n,m,k;
int d[N];
bool inq[N];
vector < pi >edge[N];

void init()
{
    for ( int i = 0 ; i <= n ; i++) edge[i].clear();

}

int spfa(int X) //X表示最大花费
{
    queue<int>q;
    ms(inq,false);
    ms(d,0x3f);
    q.push(1);
    inq[1] = true;
    d[1] = 0; // d[i]表示从1到i需要电信公司帮忙建的电话线杆的个数。
    

    while (!q.empty())
    {
    int u = q.front();
    q.pop();
    inq[u] = false;

    int siz = edge[u].size();

    for ( int i = 0 ; i < siz ; i++)
    {
        int v = edge[u][i].fst;
        int w = edge[u][i].sec>X?1:0;

        if (d[v]>d[u]+w)
        {
        d[v] = d[u] + w;
        if (inq[v]) continue;
        inq[v] = true;
        q.push(v);
        }
    }
    }
    return d[n];
    
}

void bin()
{
    int l = 0 ;
    int r = 1000000;
    int mid;
    int ans;

    while (l<=r)
    {
    mid = (l+r)/2;
    if (spfa(mid)<=k) ans = mid,r=mid-1;
    else l = mid + 1;
    }
    printf("%d\n",ans);
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif

    init();
    scanf("%d%d%d",&n,&m,&k);
    for ( int i = 1 ; i <= m ; i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        edge[u].push_back(MP(v,w));//以电话线数目为第一关键字,长度为第二关键字。
        edge[v].push_back(MP(u,w));
    }
    if (spfa(inf)==inf)
    {
        puts("-1");
        return 0;
    }
    bin();

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付