「LOJ2344」铁路票价

快来打我* 2021-10-23 13:34 323阅读 0赞

# Description #

给出一张无向图，每条边的边权都是1。依次删掉\\(q\\)条边，每一次删除后询问当前的图相较于**初始图**（每一次都与初始图比较）有多少个点到1的最短路改变了。

\\(n,m \\leq 10^5\\)

# Solution #

之前遇到过一道题是与“最短路入度”有关的，这道题也是一样。对于这类删边询问最短路的问题，都会涉及到一个概念——最短路树。在这里一个点的最短路可以从多个点转移而来，那么就得到一张“最短路图”。

我们每次删除一条边\\((u,v)\\)（假设\\(u\\)距离1更近），如果不在最短路图中，那么必定不会对点的最短路产生影响。如果在最短路图中，如果删掉之后\\(v\\)在最短路图中仍然拥有入度，那么所有点的最短路依然不会改变。如果删除这条边后\\(v\\)的入度为0了，那么到\\(v\\)的最短路就改变了。而\\(v\\)之后的节点可能也会发生变化，引起一系列“连锁反应”。这等价于\\(v\\)在最短路图中被删除了。因此我们再修改\\(v\\)的后代的入度，用\\(BFS\\)维护。

注意，这道题之所以能那么做是因为我们的最短路改变点都是相较于原图来说的。只有这样，我们才可以通过在最短路图上删边来完成，因为一旦改变一次以后就不会再改变，因此以后就不用去管了。每个点每条边都只被删一次，因此复杂度是\\(O(n+m)\\)。如果不是相较于原图而是相较于上一阶段，那么可能就要用“LCT维护最短路树”来完成了。

Meiqwq巨爷还跟我讲了另一种做法：将所有被删除的边按照其删除时间标上权值。接着倒着往图中加边，每一条最短路的形成取决于路径上时间最大的那条边的加入。而一个点到1的最短路形成时间是若干条最短路中最大时间最小的那条路径。每一次加边后\\(BFS\\)更新这个最大值，最短路形成时就是原问题中最短路改变时。

# Code #

注意在最后一步操作时要存**边**。并且标记与减入度等操作都应该在队首处进行操作。

/*DennyQi 2019*/ #include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int N = 100010; const int M = 200010; const int P = 998244353; const int INF = 0x3f3f3f3f; inline int read(){ int x(0),w(1); char c = getchar(); while(c^'-' && (c<'0' || c>'9')) c = getchar(); if(c=='-') w = -1, c = getchar(); while(c>='0' && c<='9') x = (x<<3)+(x<<1)+c-'0', c = getchar(); return x*w; } int n,m,Q,x,y,ans,res,e,d[N],rd[N],a[M],b[M],mk[M<<1],id[M<<1]; int head[N],nxt[M<<1],to[M<<1],cnte; queue <int> q; inline void add(int u, int v){ to[++cnte] = v; nxt[cnte] = head[u]; head[u] = cnte; } inline void bfs(){ d[1] = 1; q.push(1); while(!q.empty()){ int u = q.front(); q.pop(); for(int i = head[u]; i; i = nxt[i]){ if(!d[to[i]]){ d[to[i]] = d[u]+1; q.push(to[i]); } } } } inline void del(int x){ int e,u; q.push(x); while(!q.empty()){ e = q.front(); q.pop(); if(mk[e]) continue; mk[e] = 1; u = b[e]; --rd[u]; if(rd[u] == 0){ ++ans; for(int i = head[u]; i; i = nxt[i]){ if(d[u]+1 == d[to[i]]){ q.push(id[i]); } } } } } int main(){ // freopen("file.in","r",stdin); n = read(), m = read(), Q = read(); for(int i = 1; i <= m; ++i){ a[i] = read(), b[i] = read(); add(a[i],b[i]); add(b[i],a[i]); id[cnte-1] = id[cnte] = i; } bfs(); for(int i = 1; i <= n; ++i){ // printf("d[%d]=%d\n",i,d[i]); for(int j = head[i]; j; j = nxt[j]){ if(d[i]+1==d[to[j]]){ ++rd[to[j]]; } } } for(int i = 1; i <= m; ++i){ if(d[a[i]] > d[b[i]]) swap(a[i],b[i]); } while(Q--){ e = read(); if(d[a[e]]+1 == d[b[e]]){ del(e); } printf("%d\n",ans); } return 0; }

转载于:https://www.cnblogs.com/qixingzhi/p/11303373.html