AcWing 340. 通信线路

题目链接

样例解释

二分 + 最短路模型

进一步解释：题目要求我们最多把k条边置为0，使得1到N号的剩余路线中，最大的花费最小

那么我们可以假设一个解为x，只要$egd{e}_i\le x$的边都置为0。$egd{e}_i\ge x$都置为1，这样我们只关注那些等于1的边，从1到N等于1的边个数小于等于k（即要去掉边的个数$\le k$），那么这个解就是成立的！

因此这个题是可以使用二分来做的, 图示如下

到了这里，下面就是求解从1到N边权为1最少条数的路径，发现这就完美转化为了一个最短路问题。因为只有边权为0和1的边，写一个不会TLE的解法就可。还是y总的代码写得漂亮就抄y总的吧?

注意二分的起始区间是$[0,1+max(L_1,L_2,....L_m)]$, 当最终解是$1+max(L_1,L_2,....L_m)$时，表示方案无解（因为农夫的花费怎么也不可能比最大的边还要大嘛）

代码

用朴素版的dijkstra能过

#include<iostream>
#include<cstring>
using namespace std;const int N = 1e3 + 10, INF = 0x3f3f3f3f;int n, m, k;
int g[N][N];
int dist[N];
bool st[N];int dijkstra(int x)
{
    memset(st, 0, sizeof st);memset(dist, 0x3f, sizeof dist);dist[1] = 0;for(int i = 0; i < n - 1; i++){
    int u = -1;for(int j = 1; j <= n; j++){
    if(!st[j] && (u == -1 || dist[j] < dist[u])) u = j;}if(st[n]) break;st[u] = true;for(int j = 1; j <= n; j++){
    if(g[u][j] == INF) continue;int d = g[u][j] > x;dist[j] = min(dist[j], dist[u] + d);}}return dist[n];
}int main()
{
    cin >> n >> m >> k;memset(g, 0x3f, sizeof g);int maxv = -INF;for(int i = 0; i < m; i++){
    int a, b, c;cin >> a >> b >> c;g[a][b] = g[b][a] = min(c, g[a][b]);maxv = max(maxv, c);}int l = 0, r = maxv + 1;while(l < r){
    int mid = l + r >> 1;if(dijkstra(mid) <= k) r = mid;else l = mid + 1;}if(l == maxv + 1) l = -1;cout << l << endl;return 0;
}