luogu P1710 地铁涨价

一道最短路好题。

首先明确一点，把一条边的边权变成2，等于删去这条边。因为变成2后最短路肯定不会经过这条边，就相当于删去这条边了。

所以题目变成了依次删去Q条边，求每一次删完边后有几个点的最短路变大了。

多做做题就会有这么个思维：删边不好办，然而逆向加边方便多了。所以30做法就是离线逆向加边，跑Q次dijkstra。时间复杂度(Qnlogn)。

正解是基于这个暴力的：想想dijkstra更新最短路的时候，如果成功从u更新了dis[v]，那么前提一定是dis[u]已经是最短路。所以每一次我们可以不跑dijkstra，只用判断加的边(x, y)中，当前距离dis2[x]或是dis2[y]是否已经成为了最短路，如果是，就从这个点开始尝试更新他能走到的点的最短路（bfs, dfs都行，实测dfs更快）。然后如果到一个点的距离变成了最短路，ans--。

然后就是代码细节了：因为Q <= m，所以有一些边没删去，所以事先要加上，加边的时候不要每一次都判断dis2[x]或dis2[y]是否成为了最短路，而是在循环外面直接从1号节点更新，因为只有1号结点延伸出去的才可能成为最短路。而要是每一都判断dfs的话，虽然dfs会马上退出来，然而如果是一个菊花图的话，对于1号结点，每一次都遍历了很多条边，时间复杂度达到O(n²)。（这也就是我第7个点为啥一直TLE的原因……）

还有就是dis2实际上用一个bool数组就够，标记过就表示这个点已经成为了最短路，不用记录他的距离。

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #include<cctype>

 #include<vector>

 #include<stack>

 #include<queue>

 using namespace std;

 #define enter puts("")

 #define space putchar(' ')

 #define Mem(a, x) memset(a, x, sizeof(a))

 #define rg register

 typedef long long ll;

 typedef double db;

 const int INF = 0x3f3f3f3f;

 const db eps = 1e-;

 const int maxn = 1e5 + ;

 inline ll read()

 {

     ll ans = ;

     char ch = getchar(), last = ' ';

     while(!isdigit(ch)) {last = ch; ch = getchar();}

     while(isdigit(ch)) {ans = ans *  + ch - ''; ch = getchar();}

     if(last == '-') ans = -ans;

     return ans;

 }

 inline void write(ll x)

 {

     if(x < ) x = -x, putchar('-');

     if(x >= ) write(x / );

     putchar(x %  + '');

 }

 int n, m, q;

 struct Edge

 {

     int nxt, to;

 }e[maxn << ];

 int head[maxn], ecnt;

 void add(int x, int y)

 {

     e[++ecnt] = (Edge){head[x], y};

     head[x] = ecnt;

 }

 struct Node

 {

     int x, y;

 }egs[maxn << ];

 #define pr pair<int, int>

 #define mp make_pair

 bool in[maxn];

 int dis[maxn];

 void dijkstra(int s)

 {

     Mem(dis, 0x3f);

     dis[s] = ;

     priority_queue<pr, vector<pr>, greater<pr> > q;

     q.push(mp(dis[s], s));

     while(!q.empty())

     {

         int now = q.top().second; q.pop();

         if(in[now]) continue;

         in[now] = ;

         for(int i = head[now]; i != -; i = e[i].nxt)

         {

             if(dis[e[i].to] > dis[now] + )

             {

                 dis[e[i].to] = dis[now] + ;

                 q.push(mp(dis[e[i].to], e[i].to));

             }

         }

     }

 }

 bool vis[maxn << ];

 int a[maxn << ], ans[maxn << ], num;

 void solve(int now, int d)

 {

     for(int i = head[now]; i != -; i = e[i].nxt)

     {

         if(!vis[e[i].to] && d +  == dis[e[i].to])

         {

             num--;

             vis[e[i].to] = ;

             solve(e[i].to, d + );

         }

     }

 }

 int main()

 {

     Mem(head, -); ecnt = -;

     n = read(); m = read(); q = read();

     for(rg int i = ; i <= m; ++i)

     {

         egs[i].x = read(); egs[i].y = read();

         add(egs[i].x, egs[i].y); add(egs[i].y, egs[i].x);

     }

     dijkstra();

     for(rg int i = ; i <= q; ++i) a[i] = read(), vis[a[i]] = ;

     Mem(head, -); ecnt = -;

     num = n - ;

     for(int i = ; i <= m; ++i) if(!vis[i])

     {

         int x = egs[i].x, y = egs[i].y;

         add(x, y); add(y, x);

     }

     Mem(vis, ); vis[] = ;

     solve(, );

     for(rg int i = q; i; --i)

     {

         ans[i] = num;

         int x = egs[a[i]].x, y = egs[a[i]].y;

         add(x, y); add(y, x);

         if(vis[x]) solve(x, dis[x]);

         if(vis[y]) solve(y, dis[y]);

     }

     for(rg int i = ; i <= q; ++i) write(ans[i]), enter;

     return ;

 }

巴特西

luogu P1710 地铁涨价

最新文章

热门文章