首页 > 其他 > 详细

P1948 [USACO08JAN]电话线Telephone Lines

时间:2019-09-15 20:40:42      阅读:79      评论:0      收藏:0      [点我收藏+]

题目链接

  P1948 [USACO08JAN]电话线Telephone Lines

分析

  1. 简单观察题目,易得本题是求解最小最大值,宜用二分!!!
    • 证明:当存在一种有效路径时,这种路径会包含一种更小代价的有效路径(即可能是存在更小的最大值)
  2. 二分思路:在(l,r)区间内寻找符合条件的最大值,l=0,r=最大边权值
  3. 具体判断:
    1. 将题目转化为判定性问题
    2. 对边进行处理,E[].dis>mid 则此边为1,否则为0
    3. 进行dijkstra求解
    4. 若Dis[N]=inf,则不存在通路,返回false;若Dis[N]<K则返回true

具体代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=1000010;
typedef pair<int,int>node;
struct Edge
{
    int dis,next,to;
} E[maxn/2];
int Dis[1010],Head[1010],num_Edge,vis[1010];
int N,P,K,mid,MAX_DIS;
inline int Read(void)
{
    int w=0,x=0;
    char ch=0;
    while(!isdigit(ch)) w|=ch==-,ch=getchar();
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return w?-x:x;
}
inline void Add_Edge(int u,int v,int d)
{
    E[++num_Edge].dis =d;
    E[num_Edge].to =v;
    E[num_Edge].next =Head[u];
    Head[u]=num_Edge;
}
inline void Set()
{
    memset(vis,0,sizeof(vis));
    for(int i=1; i<=N; ++i)
        Dis[i]=2147483247;
    Dis[1]=0;
}
inline int Dijkstra(void)
{
    Set();
    priority_queue<node,vector<node>,greater<node> >Q;
    Q.push(make_pair(0,1));
    while(!Q.empty() )
    {
        int u=Q.top().second;
        Q.pop() ;
        if(vis[u]) continue;
        for(int i=Head[u]; i; i=E[i].next )
        {
            int v=E[i].to,dis=E[i].dis>mid?1:0;
            if(Dis[v]>Dis[u]+dis)
            {
                Dis[v]=Dis[u]+dis;
                if(!vis[v])
                    Q.push(make_pair(Dis[v],v));
            }

        }
    }
    return Dis[N];
}
int main(void)
{
    N=Read(),P=Read(),K=Read();
    for(int i=1; i<=P; ++i)
    {
        int u=Read(),v=Read(),d=Read();
        MAX_DIS=max(MAX_DIS,d);
        Add_Edge(u,v,d);
        Add_Edge(v,u,d);
    }
    int l=0,r=MAX_DIS;
    while(l<r)
    {
        mid=(l+r)/2;
        if(Dijkstra()>K)    l=mid+1;
        else r=mid;
    }
    if(l==MAX_DIS) printf("-1\n");
    else printf("%d\n",r);
    return 0;
}

 

P1948 [USACO08JAN]电话线Telephone Lines

原文:https://www.cnblogs.com/Blacktears/p/11523700.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!