P1186 玛丽卡 题解

· · 题解

洛谷P1186 玛丽卡

前言

笔者很菜，在尝试自己思路的过程中遇到了很多bug，想参考题解的时候发现本题没有任何使用二分+tarjan解题的题解，故记录之。

题目大意

给定一个 n 点 m 边的无向图，你可以任意删除一条边，求删边后最短路长度的最大值。

1 \le n \le 10^3 $ , $1 \le m \le n(n - 1) / 2

解题思路

笔者是在一场校内模拟赛中遇到的这道题，注意到本题所求的最短路长度的最大值是一个令最大值最小的问题，所以比较自然地想到二分时间 t 来求出答案。

我们考虑，在确定一个限制时间 t 后，在何种前提下满足删除一条边后 1 号点和 n 号点仍保持连通——容易想到只要使此二点在同一边双连通分量内即满足条件。

所以我们可以预先从 1 号点和 n 号点各跑一遍dijkstra，预处理出每个点到起终两点的最短路径 dis[i][0/1] ，在二分枚举限制时间 t ，以 dis[u][0] + w + dis[v][1] <= t 为判据 ，将满足条件的边全部加入新图中，跑一遍tarjan并判断 1 号点与 n 号点是否在同一连通块内即可。 该算法的时间复杂度为 O(n^2\log t) ，其中 1 \le t \le 10^6 , 1 \le n \le 10^3 ，可以通过此题。

参考代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>

using namespace std;
const int N = 1e3 + 3;
const int T = 1e6;

int n, m;
//这里的变量用于记录原图 
struct Node {
    int v, w;
    bool operator () (Node x, Node y) {
        return x.w > y.w;
    }
};
vector <Node> vec[N];
int dis[N][2]; //dis[i][0/1] 表示某个点到起点 / 终点的距离 
void dijkstra(int, int);
//这里的变量用于记录新图 
vector <Node> node[N];
stack <int> st;
int dfn[N], low[N], cl[N];
int num, ct; //num 和 ct 分别是 dfn计数器和 color计数器 
void clr(); //clear , 初始化 
void tarjan(int, int);
bool check(int);//检查在长度 l 下 , 1号点和n号点是否在同一边双中 , 若是 , 则返回true 

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        vec[u].push_back({v, w});
        vec[v].push_back({u, w});
    }
    memset(dis, 0x3f, sizeof(dis));
    dijkstra(1, 0);
    dijkstra(n, 1);

    //左闭右开的二分查找 
    int l = dis[n][0], r = T, mid;  
    while(l < r) {
        mid = l + ((r - l) >> 1);
        if(!check(mid))
            l = mid + 1;
        else r = mid;
    }
    printf("%d", l);
    return 0;
}
void dijkstra(int s, int k) {
    priority_queue <Node, vector <Node>, Node> q;
    q.push({s, 0});
    dis[s][k] = 0;
    while(!q.empty()) {
        Node tmp = q.top();
        q.pop();
        int u = tmp.v;
        int d = tmp.w;
        if(d != dis[u][k]) continue;
        //if(k == 0 && u == n) continue;
        //if(k == 1 && u == 1) continue;
        for(int i = 0; i < vec[u].size(); i ++) {
            int v = vec[u][i].v;
            int w = vec[u][i].w;
            if(d + w < dis[v][k]) {
                dis[v][k] = d + w;
                q.push({v, dis[v][k]});
            }
        }
    }

}
void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++num; st.push(u);
    for(int i = 0; i < node[u].size(); i ++) {
        int v = node[u][i].v;
        if(!dfn[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        } else if(v != fa && dfn[v] < dfn[u])
            low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]) {
        cl[u] = ++ct;
        while(st.top() != u)
            cl[st.top()] = cl[u], st.pop();
        st.pop();
    }
}
void clr() {
    num = ct = 0;
    memset(cl, 0, sizeof(cl));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    while(!st.empty()) st.pop();
    for(int i = 1; i <= n; i ++) 
        node[i].clear();
}
bool check(int l) { 
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j < vec[i].size(); j ++) {
            int v = vec[i][j].v;
            if(v > i) { //使v > u 以避免重边 
                int w = vec[i][j].w;
                if(dis[i][0] + w + dis[v][1] <= l or dis[i][1] + w + dis[v][0] <= l) {//注意一条边可能正着用也可能反着用 
                    node[i].push_back({v, w});
                    node[v].push_back({i, w});
                }
            }
        }
    }
    tarjan(1, 0);
    return cl[1] == cl[n];
}

可能存在的疑惑