「JOI 2016 Final」铁路票价

博主的 BiBi 时间

这道题的暴力我竟然打了 (SPFA)。。。（真·降智）

Solution

首先，如果这条边不在最短路上时，它之后也不会有任何贡献。那么之后的边就是指在最短路上的边。

我们可以确定，当一条边被加上权值时，这条边相当于被删除了。因为它再也不可能是最短路了。

可以发现，当一个点前面的最短路边都被删了，那么这个点往后延伸的边也是没用的了。（感觉有点像拓扑）

接下来就可以码出来了，首先我们跑一遍 (BFS)，这样通过 (dis) 数组的比较就可以判断是否是在最短路上的边，再搞一个类似入度的东西就好了。

时间复杂度应该是 (O(m*2))？

Code

#include <cstdio>
#include <queue>
#include <iostream>
using namespace std;

const int N = 1e5 + 5;

bool vis[N << 1];
int u[N << 1], v[N << 1], in[N], cnt, ans, n, m, Q, dis[N], goal, dot[N << 2], nxt[N << 2], head[N];
queue <int> q;

void addEdge(const int u, const int v) {
    dot[++ cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
}

void bfs() {
    q.push(1); dis[1] = 1;
    while(! q.empty()) {
        int u = q.front(); q.pop();
        for(int i = head[u]; i; i = nxt[i]) {
            int v = dot[i];
            if(! dis[v]) dis[v] = dis[u] + 1, q.push(v);
        }
    }
}

void del() {
    q.push(goal);
    while(! q.empty()) {
        int e = q.front(); q.pop();
        if(vis[e]) continue;//这里是时间复杂度的保证，显然删过一次就不用再删了
        vis[e] = 1;
        int p = v[e]; -- in[p];
        if(in[p] == 0) {
            ++ ans;
            for(int i = head[p]; i; i = nxt[i])
                if(dis[p] + 1 == dis[dot[i]]) q.push(i + 1 >> 1);
        }
    }
}

int main() {
    //freopen("price.in", "r", stdin); freopen("price.out", "w", stdout);
    scanf("%d %d %d", &n, &m, &Q);
    for(int i = 1; i <= m; ++ i) {
        scanf("%d %d", &u[i], &v[i]);
        addEdge(u[i], v[i]), addEdge(v[i], u[i]);
    }
    bfs();
    for(int i = 1; i <= n; ++ i)
        for(int j = head[i]; j; j = nxt[j])
            if(dis[i] + 1 == dis[dot[j]]) ++ in[dot[j]];
    for(int i = 1; i <= m; ++ i)
        if(dis[u[i]] > dis[v[i]]) swap(u[i], v[i]);
    while(Q --) {
        scanf("%d", &goal);
        if(dis[u[goal]] + 1 == dis[v[goal]]) del();
        printf("%d
", ans);
    }
    return 0;
}