题解 P1710 【地铁涨价】

转化问题

这里路线涨价明显等同于删边，所以我们可以把问题倒过来思考：

图上依次(倒序)加边，问每个点成为最终图最短路的时间

分析

记*原图*的点1到达点i的最短路为dis[i]，*当前状态*下点1到达点i最短路为d[i]。下面称d[i]==dis[i]的点i为扩展点。

通过分析最短路性质发现，某个点v新成为扩展点情况有两个

1. 加边(u,v)更新，且dis[u]==d[u]&&dis[v]==d[u]+1&&d[v]!=dis[v]。

2. 邻居u突然成为最终图最短路，且dis[v]==d[u]+1&&d[v]!=dis[v]

_(其实上面是同一种情况XD)_

重要的是，每个点只会被更新1次，体现在了上面的强调处。这是很显然的，因为这题答案是唯一确定的，但这个是降低复杂度的重要条件。

确定算法

1. 首先把最终图的最短路情况dis[i]求出来。然后重建图，去掉所有待加边。

2. 然后依次加入待加边，检测边的两端是否符合条件1，若符合，则进行深度优先搜索，对新成为扩展点邻居进行条件2判断。

3. 将每次新成为扩展点的数目记录，最后处理出答案。

复杂度分析

1. 由于边权为1，求dis[]可以用bfs遍历，复杂度为O(n+m)。

2. 加入了q条边，在整个过程2中每个点只会被dfs到一次，所以复杂度为O(n+m+q)。

3. 每一次的答案是新成为扩展点的数目，所以需要一遍前缀和，复杂度为O(q)。

最终复杂度为O(n+m+q)

代码

#include<bits/stdc++.h>
#define maxn 400010
using namespace std;
#define G c=getchar()
inline int read()
{
    int x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
#define AE(u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++
int to[maxn],nxt[maxn],idx[maxn],Si;
int n,m,q,dis[maxn],d[maxn];
queue<int>Q;
int vis[maxn],b[maxn];
int E[maxn][2],qq[maxn],ans[maxn],tmp;
void dfs(int u,int fa)
{
    for(int i=idx[u];i+1;i=nxt[i])
        if(to[i]!=fa&&dis[to[i]]==d[u]+1&&dis[to[i]]!=d[to[i]])
        {
            d[to[i]]=d[u]+1;tmp++;
            dfs(to[i],u);
        }
}
void bfs(int s,int dis[])
{
    while(!Q.empty())Q.pop();
    Q.push(s);dis[s]=0;vis[s]=1;
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int i=idx[u],v;i+1;i=nxt[i])
        {
            if(vis[v=to[i]])continue;
            dis[v]=dis[u]+1;
            Q.push(v);vis[v]=1;
        }
    }
}
int main()
{
    memset(idx,-1,sizeof(idx));
    n=read(),m=read(),q=read();
    for(int i=1;i<=m;i++)
        E[i][0]=read(),E[i][1]=read(),AE(E[i][0],E[i][1]),AE(E[i][1],E[i][0]);
    bfs(1,dis);
    memset(idx,-1,sizeof(idx));Si=0;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=q;i++)qq[i]=read(),b[qq[i]]=1;
    for(int i=1;i<=m;i++)
        if(!b[i])AE(E[i][0],E[i][1]),AE(E[i][1],E[i][0]);
    bfs(1,d);
    for(int i=q;i>=1;i--)
    {
        int x=qq[i],u=E[x][0],v=E[x][1];tmp=0;
        if(dis[u]==d[u]&&dis[v]==d[u]+1&&d[v]!=dis[v])tmp++,d[v]=dis[v],dfs(v,u);
        swap(u,v);
        if(dis[u]==d[u]&&dis[v]==d[u]+1&&d[v]!=dis[v])tmp++,d[v]=dis[v],dfs(v,u);
        AE(u,v),AE(v,u);
        ans[i]=tmp;
    }
    for(int i=1;i<=q;i++)
        ans[i]+=ans[i-1],printf("%d\n",ans[i]);
}