AcWing340通信道路/ USACO2008 Telephone Line S

解题思路

首先可以得到一个很容易得到的贪心策略，将一条路径上最贵的（边权最大）的\(K\)条边删去，那么我们剩下的路径中最贵（边权最大）的路就是原本这条路径上帝\(K + 1\)大的路。

于是原问题就可以转化为：

求一张无向图中最大的一条路径中的第\(K+1\)大的边

这就启发我们枚举所有的路径。

可行吗？

显然是不可行的，这个路很多，但是我们可以反向思考

我们可以假定一个距离\(x\)，然后看看这张图上是否存在一条路径，使它上面第\(K + 1\)大的边长度为\(x\),进一步的，我们可以转化成为在这张图中，是否存在\(K\)条边，任意一条边的权重\(W_{i}>x\)

这样我们的\(check\)函数似乎就呼之欲出了

check函数

这里的\(check\)我们判断一张图中是否有\(K\)条权重大于\(x\)的边，可以进行一下转换：

对于边权\(W_{i} > x\) 的边，设置权重\(w_{i} = 1\)（这是小w，不是原题给定权重）

反之设置权重\(w_{i} = 0\)

然后跑下这张图的最短路(\(从1到N\)),判断是否\(\le k\)即可

Dijkstra写法 \(O(mlog^{2}n)\)

这没什么好说的，就是建图跑最短路，因为边权非负（只能是\(0或1\)）

#include <iostream>

#include <cstring>

#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 20020;

int h[N], e[N], w[N], ne[N], idx;

int dist[N], st[N], n, m, k;

void add(int a, int b, int c)

{

    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;

}

bool check(int x)

{

    memset(dist, 0x3f, sizeof dist);

    memset(st, 0, sizeof st);

    priority_queue<PII, vector<PII>, greater<> > heap;

    dist[1] = 0, heap.push({dist[1], 1});

    while (heap.size())

    {

        auto t = heap.top().second; heap.pop();

        if (st[t]) continue ;

        st[t] = true ;

        for (int i = h[t]; ~i; i = ne[i])

        {

            int j = e[i], W = (w[i] > x);

            if (dist[j] > dist[t] + W)

            {

                dist[j] = dist[t] + W;

                heap.push({dist[j], j});

            }

        }

    }

    return dist[n] <= k;

}

int main()

{

    scanf("%d%d%d", &n, &m, &k);

    memset(h, -1, sizeof h);

    while (m -- )

    {

        int u, v, w;

        scanf("%d%d%d", &u, &v, &w);

        add(u, v, w), add(v, u, w);

    }

    int l = 0, r = 1e6 + 1;

    while (l < r)

    {

        int mid = l + r >> 1;

        if (check(mid)) r = mid;

        else l = mid + 1;

    }

    if (r == 1e6 + 1) r = -1;

    printf("%d\n", r);

    return 0;

}

双端队列广搜 \(O(mlogn)\)

因为边权只有\(0-1\)，可以用双端队列广搜，时间是线性的，再乘上二分次数，是\(O(mlogn)\)

#include <iostream>

#include <cstring>

#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 20020;

int h[N], e[N], w[N], ne[N], idx;

int dist[N], st[N], n, m, k;

void add(int a, int b, int c)

{

    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;

}

bool check(int x)

{

    memset(dist, 0x3f, sizeof dist);

    memset(st, 0, sizeof st);

    deque<int> dq;

    dist[1] = 0, dq.push_back(1);

    while (dq.size())

    {

        int t = dq.front(); dq.pop_front();

        if (st[t]) continue ;

        st[t] = true ;

        for (int i = h[t]; ~i; i = ne[i])

        {

            int j = e[i], W = (w[i] > x);

            if (dist[j] > dist[t] + W)

            {

                dist[j] = dist[t] + W;

                if (W) dq.push_back(j);

                else dq.push_front(j);

            }

        }

    }

    return dist[n] <= k;

}

int main()

{

    scanf("%d%d%d", &n, &m, &k);

    memset(h, -1, sizeof h);

    while (m -- )

    {

        int u, v, w;

        scanf("%d%d%d", &u, &v, &w);

        add(u, v, w), add(v, u, w);

    }

    int l = 0, r = 1e6 + 1;

    while (l < r)

    {

        int mid = l + r >> 1;

        if (check(mid)) r = mid;

        else l = mid + 1;

    }

    if (r == 1e6 + 1) r = -1;

    printf("%d\n", r);

    return 0;

}

SPFA \(O(mlogn\sim 被卡飞)\)

和Dijkstra一样，跑个最短路

#include <iostream>

#include <cstring>

#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 20020;

int h[N], e[N], w[N], ne[N], idx;

int dist[N], st[N], n, m, k;

void add(int a, int b, int c)

{

    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;

}

bool check(int x)

{

    memset(dist, 0x3f, sizeof dist);

    memset(st, 0, sizeof st);

    queue<int> q;

    dist[1] = 0, q.push(1), st[1] = true;

    while (q.size())

    {

        int t = q.front(); q.pop();

        st[t] = false ;

        for (int i = h[t]; ~i; i = ne[i])

        {

            int j = e[i], W = (w[i] > x);

            if (dist[j] > dist[t] + W)

            {

                dist[j] = dist[t] + W;

                if (!st[j]) q.push(j), st[j] = true ;

            }

        }

    }

    return dist[n] <= k;

}

int main()

{

    scanf("%d%d%d", &n, &m, &k);

    memset(h, -1, sizeof h);

    while (m -- )

    {

        int u, v, w;

        scanf("%d%d%d", &u, &v, &w);

        add(u, v, w), add(v, u, w);

    }

    int l = 0, r = 1e6 + 1;

    while (l < r)

    {

        int mid = l + r >> 1;

        if (check(mid)) r = mid;

        else l = mid + 1;

    }

    if (r == 1e6 + 1) r = -1;

    printf("%d\n", r);

    return 0;

}

关于时间

\(AcWing:Dijkstra\ 150ms，双端队列BFS\ \ 56ms，SPFA\ 63ms\)

\(Luogu:Dijkstra\ 238ms, 双端队列BFS\ 73ms， SPFA\ 89ms\)

巴特西