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

· · 题解

自认为很清奇的思路

%你赛用了30min憋出来的思路，较好理解，适用于初学者，跑的有点慢。

总思路: 最短路+二分 (Dijkstra堆优化)最短路

思路描述

仔细理解了一下题意，是让求一个最大的最小，那么很显然具有单调性，二分答案是没跑了。众所周知，二分答案的难点在于check函数，那么怎么检验一个答案是否合法呢？

提取一下题意，就知道只要至少有一条路径中边的边权大于所二分的答案的条数≤k就合法。

其实我一开始想的是DFS,写挂了才想出这个思路

然后怎么实现呢？首先考虑最短路，思考能不能用最短路维护出一条路径中边的边权大于所二分的答案的条数。仔细想一下是可以的。具体实现步骤如下：

首先我们将所有边权都减去你二分到的答案（下图以样例为例，二分到的答案为4）：

那么这有什么用呢？很显然，图中所有权值≤0的边权都是小于所枚举到的答案的，所以只有＞0的权值对答案有贡献。我们重新定义一个权值，此权值＞0的所有边的新边权为1，≤0的则为0，由于只要有一条路径满足条件即可，所以只要跑最短路就可以了。

新权值图：

跑出最短路的值和k相比较，如果≤k就返回true，否则返回false。这道题就做完了。

AC代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 0x7fffffff
const int maxn=1e3+1;
const int maxp=1e4+1;
using namespace std;
struct jg{
    int dis,jd;
    bool operator < (const jg &a) const{
        return a.dis<dis;
    }
};
struct Edge{
    int next,to,worth,gx;
}e[maxp*2];
int head[maxn],cnt,ans=inf,dis[maxn];
int ma,mi=inf;
int n,p,k;
bool vis[maxn];
void add(int from,int to,int worth)
{
    e[++cnt].next=head[from];
    e[cnt].to=to;
    e[cnt].worth=worth;
    head[from]=cnt;
}
void dijkstra()
{
    priority_queue<jg> q;
    for(int i=1;i<=n;i++) dis[i]=inf;
    dis[1]=0;
    q.push((jg){0,1});
    while(!q.empty())
    {
        jg now=q.top();
        q.pop();
        if(vis[now.jd]) continue;
        vis[now.jd]=true;
        for(int i=head[now.jd];i;i=e[i].next)
            if(dis[e[i].to]>dis[now.jd]+e[i].gx)
            {
                dis[e[i].to]=dis[now.jd]+e[i].gx;
                q.push((jg){dis[e[i].to],e[i].to});
            }
    }
}
bool check(int in)
{
    memset(vis,0,n+1);
    for(int i=1;i<=cnt;i++)
    {
        e[i].worth-=in; 
        if(e[i].worth>0) e[i].gx=1;
        else e[i].gx=0; 
    }
    dijkstra();
    for(int i=1;i<=cnt;i++)
        e[i].worth+=in;
    if(dis[n]<=k) return true;
    else return false;
}
int mian()
{
//  freopen("line.in","r",stdin);
//  freopen("line.out","w",stdout);
    scanf("%d%d%d",&n,&p,&k);
    for(int i=1;i<=p;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
        ma=max(z,ma);
        mi=min(z,mi);
    }
    int l=mi-1,r=ma+1,mid;
    while(l<=r)
    {
        mid=(l+r)>>1; 
        if(check(mid))
        {
        r=mid-1;
        ans=min(ans,mid);           
        }
        else
        l=mid+1;
    }
    printf("%d",ans);
    return 0;
}