#\(\mathcal{\color{red}{Description}}\)

给定一个图，请你求出在把其中自由选择的\(k\)条的权值都置为零的情况下，图中\(1-N\)最短路上的最大边权的最小值。

#\(\mathcal{\color{red}{Solution}}\)

哇这个题真是吊打我的智商啊…

首先我们看题目中给的限制条件，限制我们不能直接\(sort\)一遍的条件就是我们要找的是最短路上的边权最大值最小限制了我们把一些边的权值置为零之后，图上的最短路。而这个最短路的情况比较复杂，因为你不可以静态删边，\(DP\)的话应该可以，但是\(DP\)起来不容易定义状态并且转移较麻烦其实就是我不会。所以我们考虑把每种合法的状态都枚举一遍，得出\(min\)。但是比较显然的是，由于结果具有某种意义上的单调性，所以我们可以二分。

那怎么二分呢？我们可以考虑二分一条扫描线，把大于这条边的边权都设成\(1\)，小于的都设成\(0\)。如果\(SPFA\)出来的结果\(\leq K\)的话，那这就是一种合法的方案；否则不合法。

然后就二分就行了惹~

// luogu-judger-enable-o2

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#define to(k) e[k].to

using namespace std ;

const int MAXN = 12050 ;

struct edge{

    int to, next, v ;

}e[MAXN << 1] ;

queue<int> q ;

int head[MAXN << 1], cnt, dist[MAXN], i, k, ct ;

int l, r, mid, a, b, c, N, M, K, vis[MAXN], now ;

inline void init(){

    memset(dist, 0x3f, sizeof(dist)), memset(vis, 0, sizeof(vis)) ;

    queue<int> emt ; swap(q, emt), q.push(1), vis[1] = 1, dist[1] = 0  ;

}

inline bool check(int x){

    init() ;

    while(!q.empty()){

        now = q.front(), q.pop(), vis[now] = 0 ;

        for(k = head[now]; k ; k = e[k].next){

            ct = (e[k].v > x ? 1 : 0) ;

            if(dist[to(k)] > dist[now] + ct){

                dist[to(k)] = dist[now] + ct ;

                if(!vis[to(k)]){

                    vis[to(k)] = 1 ;

                    q.push(to(k)) ;

                }

            }

        }

    }

    if(dist[N] > K) return 0 ; return 1 ;

}

inline void add(int u, int v, int w){

    e[++cnt].to = v, e[cnt].v = w ;

    e[cnt].next = head[u], head[u] = cnt ;

}

int main(){

    cin >> N >> M >> K ;

    for(i = 1; i <= M; i ++){

        cin >> a >> b >> c ;

        add(a, b, c), add(b, a, c) ;

    }l = 0, r = 1000000 ;

    while(l < r){

        mid = (l + r) >> 1 ;

        if(check(mid)) r = mid ;

        else  l = mid + 1 ;

    }

    if(l == 1000000) cout << -1 ;

    else cout << l ;

}

幕后花絮：这道题由于我忘了判\(-1 +\)空间开小导致挂了好多次……真是\(GG\)

巴特西

[USACO08JAN]电话线$Telephone \ \ Lines$（图论$+SPFA+$ 二分答案）

#\(\mathcal{\color{red}{Description}}\)

#\(\mathcal{\color{red}{Solution}}\)

最新文章

热门文章