算法提高课汇总

模型抽象

• $N$座通信基站, $P$条双向电缆: $N$个顶点的无向图.

• 优惠活动: 假设某条路径权值降序排列后$w_1, w_2, …, w_k, w_{k+1}, …, w_l$. 那么可选的花费为
  $w_1\sim w_{k+1}$, 因为我们最多可以让前$k$条电缆免费. 若$l\le k$, 则可以让路线上所有电缆免费,
  即花费最小为$0$.

题目求价格最贵花费的最小值, 考虑用二分求解.

二分思路

二分的本质是选择一个属性, 可以将序列分为两部分, 一部分满足, 另一部分不满足. 且随着属性值的变化,
满足的部分也会线性变化. 而二分求解的思路是每次迭代保证满足性质的部分始终在$[l, r]$之间, 迭代的
最后$l = r =\;$最终解.

本题中一个最先想到的可能属性是最终的花费$w$, 下面判断$w$的取值是否满足二分属性的特点:

• 考虑如何判断花费$w$是合法的: 即是否存在从$1$到$N$的路径$w_1, w_2, …, w_l$, 使得$w_1\le w\le w_{k+1}$,
  也就是$w$在可选的花费之间; 或者是否存在一条路径, 使得路径权值满足$w_i\gt w$的数目不超过$k$个.

• 如果$w$值增加, 那么存在上述路径的数目也会增加: 考虑极端情况, 若$w = \infty$, 则在$1$到$N$
  联通的情况下所有路径都满足上述条件.

题目可转化为考虑对任意$w$, 判断图中是否存在路径满足上述条件, 通过二分求满足条件的最小$w$.

最短路问题

对于每个边权, 我们考虑的仅仅是其是否大于$w$, 考虑将所有边权以是否大于$w$赋值, 若$w_i\gt w$,
则在图中将其视为$1$, 否则视为$0$.

通过上述变换后对$w$是否合法的判断可以转变为最短路问题: 从$1$到$N$所有路径中边权大于$w$的边权的
个数的最小值.

代码实现

注意: 二分区间$[0, 1000001]$:

• $0$: $l\le k$的情况, 即花费为$0$.

• 电缆花费最大值$+1$: 用于区分$1$到$N$不连通和可能的最大花费.

二分$+$双端队列$bfs$

#include <queue>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e3 + 10, M = 2e4 + 10, L = 1e6;

int n, m, k;
int h[N], e[M], w[M], ne[M], idx;
int dist[N]; bool st[N]; //双端队列bfs

void add(int u, int v, int c)
{
    e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx ++;
}

//双端队列bfs判断花费x是否合法
bool check(int x)
{
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    deque<int> que;
    que.push_front(1); //权值为0/1 此时双端队列与优先队列等价

    //算法思路类似堆优化的djkstra
    while( que.size() )
    {
        int u = que.front(); que.pop_front();

        if( st[u] ) continue;
        else st[u] = true;

        for( int i = h[u]; ~i; i = ne[i] )
        {
            int v = e[i], c = w[i] > x; //大于花费置为1 否则为0
            if( dist[v] > dist[u] + c )
            {
                dist[v] = dist[u] + c;
                if( !c ) que.push_front(v);
                else que.push_back(v);
            }
        }
    }
    return dist[n] <= k; //判断所有路径中权值大于x的边的数目的最小值是否<=k
}

int main()
{
    cin >> n >> m >> k;

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    //二分
    int l = 0, r = L + 1;
    while ( l < r )
    {
        int mid = l + r >> 1;
        if( check(mid) ) r = mid;
        else l = mid + 1;
    }
    if( r == L + 1 )    r = -1; //1到N不连通
    cout << r << endl;

    return 0;
}