洛谷P1710 地铁涨价

2022-05-06 02:34:38

P1710 地铁涨价

51通过
339提交
题目提供者洛谷OnlineJudge
标签O2优化云端评测2
难度提高+/省选-

提交讨论题解

最新讨论

求教：为什么只有40分
数组大小一定要开够啊...
如果强制在线会怎么样
请问为什么第二段铁路变化后…
话说这题和初赛的最后一个大…

题目背景

本题开O2优化，请注意常数

题目描述

博艾市除了有海底高铁连接*、*与日本，市区里也有很成熟的轨道交通系统。我们可以认为博艾地铁系统是一个无向连通图。博艾有N个地铁站，同时有M小段地铁连接两个不同的站。

地铁计价方式很简单。从A站到B站，每经过一小段铁路（连接直接相邻的两个点的一条边），就要收取1博艾元。也就是说，从A站到B站，选择的路径不一样，要价也会不同。

我们认为凡华中学在1号地铁站。学生们通过地铁通勤，他们当然知道选择最短路来坐车的话，票价最便宜。

然而博艾地铁公司经营不善，一直亏损，于是他们打算提价。提价一次就是将一小段铁路原来收费1元改收2元。同一小段的铁路不会多次提价。他们打算提价Q次。

学生们知道，如果他们到学校的一条最短路径中的一小段提价了，可以改变路径，使总票价不变。然而随着一条一条的铁路被提价，当居住在某个站附近的学生发现，提价后，没有任何一种方案可以从家到学校的费用和初始费用相等时，就会不满。

现在地铁公司希望知道，对于每一次涨价，有多少个站，学生会因为涨价而不满呢？

输入输出格式

输入格式：

第一行为三个整数N,M,Q。

接下来M行，每行2个整数ai,bi,表示第i条铁路连接的两个站。i表示铁路编号。

接下来Q行，每行一行整数rj，表示每次涨价的铁路编号。

输出格式：

Q行。每行一个整数表示不满的车站数量。

输入输出样例

输入样例#1：

5 6 5

1 2

1 3

4 2

3 2

2 5

5 3

输出样例#1：

说明

【样例解释】

次数车站2 车站3 车站4 车站5

初始 1 1 2 2

1 1 1 2 2

2 1 2 2 3

3 1 2 2 3

4 2 2 3 3

5 2 2 4 3

【数据范围】

对于20%的数据 N≤100, Q≤30

对于40%的数据 Q≤30

对于70%的数据正确的输出结果中，不会有超过50种不一样的整数（数据范围剧透解法系列）

对于100%的数据 N≤100000, Q≤M≤200000

分析：难度比较大的一题，如果先求出最短路，然后删边再求一次最短路能得40分，必须要提高效率.首先，删的边只有在从1到每个点的最短路上才有用，我们可以用bfs求出最短路图，即1到每个点的最短路的图，判断一条边删掉之后有多少个点的最短路会变，那么从1到这个点的最短路数量一定多于1，会发现并不好记录到每个点的最短路数量，那么我们可以把原本的无向图变成一个DAG,即求最短路图的时候只连一条边,我们在求出最短路图的时候顺便记录下每个点的父亲数，这样的话能判断最短路的数量.

然后开始删边，这里不能单单只删两个点，可能两个点都被记录了但不是同一条边，正确的做法是记录边。如果删的这条边是最短路图上的边，那么从这条边指向的点开始dfs,如果这个点的父亲数-1后恰好等于0，那么1到这个点的最短路被改变了，从这个点开始继续dfs,标记被删边影响到的点.

当然，可以考虑离线做法，即将删边变成加边，不过dfs的意义和删边恰好相反，知道可以这么做即可。

不过本题的数据非常诡异，数组的大小要非常小心的确定，不然就会70分.

70分加边代码：

#include <cstdio>

#include <iostream>

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;

const int maxn = ;

int n, m, q,cnt = ,d1[maxn],ans[maxn],qq[maxn],pd[maxn],vis[maxn],flag[maxn],viss[maxn];

int head[maxn], to[maxn], nextt[maxn], tot1 = ;

int head1[maxn], to1[maxn], nextt1[maxn], tot2;

struct node

{

    int x, y;

}e[maxn];

void add(int x, int y)

{

    tot1++;

    to[tot1] = y;

    nextt[tot1] = head[x];

    head[x] = tot1;

}

void add2(int x, int y)

{

    tot2++;

    to1[tot2] = y;

    nextt1[tot2] = head1[x];

    head1[x] = tot2;

}

void bfs1()

{

    queue <int> q;

    viss[] = ;

    q.push();

    while (!q.empty())

    {

        int u = q.front();

        q.pop();

        for (int i = head[u]; i; i = nextt[i])

        {

            int v = to[i];

            if (!viss[v])

            {

                d1[v] = d1[u] + ;

                q.push(v);

                viss[v] = ;

            }

        }

    }

}

void bfs2()

{

    memset(viss, , sizeof(viss));

    queue <int> q;

    viss[] = ;

    q.push();

    while (!q.empty())

    {

        int u = q.front();

        q.pop();

        for (int i = head[u]; i; i = nextt[i])

        {

            int v = to[i];

            if (d1[v] == d1[u] + )

                flag[i / ] = ;

            if (!viss[v])

            {

                viss[v] = ;

                q.push(v);

            }

        }

    }

}

void dfs(int u)

{

    cnt++;

    vis[u] = ;

    for (int i = head1[u]; i; i = nextt1[i])

    {

        int v = to1[i];

        if (!vis[v])

            dfs(v);

    }

}

int main()

{

    scanf("%d%d%d", &n, &m, &q);

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

    {

        int a, b;

        scanf("%d%d", &a, &b);

        e[i].x = a, e[i].y = b;

        add(a, b);

        add(b, a);

    }

    bfs1();

    bfs2();

    for (int i = ; i <= q; i++)

    {

        int a;

        scanf("%d", &a);

        pd[a] = ;

        qq[i] = a;

    }

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

        if (d1[e[i].x] > d1[e[i].y])

            swap(e[i].x, e[i].y);

    vis[] = ,cnt = ;

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

        if (!pd[i] && flag[i])

        {

        if (vis[e[i].x] && vis[e[i].y])

            continue;

        add2(e[i].x, e[i].y);

        if (vis[e[i].x])

            dfs(e[i].y);

        }

    ans[q] = n - cnt;

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

    {

        int temp = qq[i + ];

        //if (e[temp].x && e[temp].y)

            //continue;

        if (!(vis[e[temp].x] && vis[e[temp].y]) && flag[temp])

            add2(e[i].x, e[i].y);

        if (vis[e[temp].x] && flag[temp] && !vis[e[temp].y])

            dfs(e[temp].y);

        ans[i] = n - cnt;

    }

    for (int i = ; i <= q; i++)

        printf("%d\n", ans[i]);

    //while (1);

    return ;

}

AC代码:

#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

#include <queue>

#include <stack>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#define INF 0x3f3f3f3f

#define LL long long

using namespace std;

struct Edge {

    int u, v;

} edge[];

int n, m, q, B, ans = ;

vector<int> aG[];

vector<int> G[];

int fa[];

int query[];

queue<int> Q;

int d[];

int r_u[], r_v[];

bool vis[];

bool cnt[];

inline int min(int x, int y) { return x > y ? y : x; }

inline int max(int x, int y) { return x < y ? y : x; }

inline void addedge2(int a, int b) {

    edge[B].u = a, edge[B].v = b;

    aG[a].push_back(B++);

}

inline void addedge(int a, int b) {

    edge[B].u = a, edge[B].v = b;

    fa[b] ++;

    G[a].push_back(B++);

}

inline void in() {

    int i, a, b, c;

    scanf("%d%d%d", &n, &m, &q);

    for (i = ; i <= m; i++) {

        scanf("%d%d", &a, &b);

        addedge2(a, b);

        addedge2(b, a);

        r_u[i] = a, r_v[i] = b;

    }

    for (i = ; i < q; i++) scanf("%d", query + i);

}

inline void BFS() {

    int sz, x, i;

    memset(d, 0x3f, sizeof(d));

    vis[] = , d[] = , Q.push();

    while (!Q.empty()) {

        x = Q.front(); Q.pop();

        sz = aG[x].size();

        for (i = ; i < sz; i++) {

            Edge& e = edge[aG[x][i]];

            if (d[e.v] == d[x] + ) addedge(x, e.v);

            if (!vis[e.v]) {

                d[e.v] = d[x] + , addedge(x, e.v);

                vis[e.v] = ;

                Q.push(e.v);

            }

        }

    }

}

inline void _del(int x) {

    cnt[x] = ;

    int i, u = edge[x].u, v = edge[x].v;

    fa[v] --;

    if (fa[v] >=  || fa[v] < ) return;

    ans++;

    //cout << v <<' '<<fa[v] << endl;

    int sz = G[v].size();

    for (i = ; i < sz; i++) {

        Edge& e = edge[G[v][i]];

        if (!cnt[G[v][i]] && d[e.v] == d[v] + ) _del(G[v][i]);

    }

}

//建最短路DAG，然后删边时看看儿子的所有父亲能不能连过来，能的话就不变，不能的话说明儿子不是最短路了，需要切除其所有出边，重复刚刚的过程

inline void solve() {

    int i, j;

    BFS();

    for (i = ; i <= m; i++) {

        if (d[r_u[i]] > d[r_v[i]]) swap(r_u[i], r_v[i]);

    }

    for (i = ; i < q; i++) {

        int sz = G[r_u[query[i]]].size();

        for (j = ; j < sz; j++) {

            Edge& e = edge[G[r_u[query[i]]][j]];

            if (e.v == r_v[query[i]]) {

                if (!cnt[G[r_u[query[i]]][j]])

                    _del(G[r_u[query[i]]][j]);

                break;

            }

        }

        printf("%d\n", ans);

    }

}

int main() {

    in();

    solve();

    return ;

}

码农公寓

相关文章