P1948 [USACO08JAN]Telephone Lines S做题笔记

Jason12 · 2022-06-12 22:09:24 · 个人记录

初学 SPFA 时在书上看到了这题，，书上给了两个解法，一个是用 SPFA 来 dp，另一个是二分答案 + SPFA。本来想写第一种，结果翻遍了题解区（因为不会实现），也没找到一片清晰易懂的这种做法的题解，只好写第二种。具体思路是二分第 k+1 长的电话线的长度，用 SPFA 作为 check 函数，如果长度在二分出的第 k+1 长的电话线的长度之上的电话线数量 \le k，就更新答案，知道不能再更新为止。

#include <bits/stdc++.h>
  using namespace std;
int n,m,k,o,l,r,t,u,v,w,b[1005],s[1005],ans=-1,i;
bool c[1005];
struct xy{
    int x,y,z;
}a[20005];
queue<int>q;
void Add()
{
    a[++o].x=b[u];
    b[u]=o;
    a[o].y=v;
    a[o].z=w;
    a[++o].x=b[v];
    b[v]=o;
    a[o].y=u;
    a[o].z=w;
}
bool check()
{
    int j,p,d;
    memset(s,0x7f,sizeof(s));
    memset(c,0,sizeof(c));
    s[1]=0;
    c[1]=1;
    q.push(1);
    while (!q.empty())
    {
        p=q.front();
        q.pop();
        for (j=b[p];j;j=a[j].x)
        {
            if (a[j].z>t) d=s[p]+1;
            else d=s[p];
            if (d<s[a[j].y])
            {
                s[a[j].y]=d;
                if (!c[a[j].y])
                {
                    q.push(a[j].y);
                    c[a[j].y]=1;
                }
            }
        }
        c[p]=0;
    }
    if (s[n]<=k) return 1;
    return 0;
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(nullptr);
    cin>>n>>m>>k;
    for (i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        Add();
    }
    l=0;
    r=1e6;
    ans=-1;
    while (l<=r)
    {
        t=(l+r)>>1;
        if (check())
        {
            ans=t;
            r=t-1;
        }
        else l=t+1;
    }
    cout<<ans<<endl;
    return 0;
}