站外题求助

调了 n 小时，没调出来，问了AI也没调出来。

Problem G: 铁路运费

Time Limit: 1 Sec Memory Limit: 128 MB

Description

CSSYZ国有N个城市，依次编号为1, 2, …, N。城市1是CSSYZ国的首都。该国的铁路公司只有1家，由FYT垄断经营，FYT公司运营着M条路线。路线被编号为1, 2, …, M，第i条线路(1<=i<=M)双向连接着城市Ui和城市Vi。城市间的移动方式只有铁路。任意两个城市之间都能通过若干条铁路互通，即任意两个城市之间，直接连接的路线最多只有1条；对于任一城市，从该市总是可以通过若干条路线到达城市1。

现在所有路线的运费都是1元。陷于经营困境的FYT计划在今后Q年间提高若干条路线的运费。在这个计划里，第j年(1<=j<=Q)的年初将把路线Rj的运费从1元提升到2元。被提价过一次的路线的运费将一直是2元，不会再次提价。此外，FYT的铁路公司每年还会调查每个城市的市民的满意度。计划开始前，每个城市的市民都表示满意，但提价之后，可能会出现表示不满的市民。每年的满意度调查都在当年的提价完成之后进行。所以进行第j年(1<=j<=Q)的满意度调查时，路线R1, R2, …, Rj的运费提升已经完成，此外的路线还没有被提价。第j年的满意度调查里，如果城市k(2<=k<=N)的市民从城市k到首都城市1的费用的最小值比计划开始前的最小费用要高，则会对铁路公司表示不满。

如果路线经过多条铁路，费用是各条路线的运费的和。城市1的市民不会对铁路公司表示不满。另外请注意，提价后获得最小费用要使用的路线可能跟计划开始前的不一样。在整个计划开始之前，对于今后Q年间市民的满意度调查，FYT希望计算存在不满市民的城市个数。请写出一个程序，给定CSSYZ国的铁路路线信息和提价计划，输出每次满意度调查里存在不满市民的城市个数。

Input

第一行为3个用空格隔开的整数N, M, Q。N为城市个数，M为路线条数，Q为提价计划的执行年数。

接下来M行中第i行(1<=i<=M)为两个用空格隔开的整数Ui, Vi，表示第i条路线连接着城市Ui和Vi。

接下来Q行中第j行(1<=j<=Q)为整数Rj，表示计划的第j年将提升路线Rj的运费。

Output

输出Q行，第j行(1<=j<=Q)表示第j年的满意度调查中存在不满市民的城市个数。

Sample Input

CPP

Sample Output

CPP

【输出样例1】
0
2
2
4
4
【输出样例2】
1
1
2
2
3
3

【数据范围】

25%的数据满足：N<=100，M<=4 950，Q<=30；

50%的数据满足：Q<=30；

75%的数据满足：输出结果里出现的不同数最多50种；

100%的数据满足：2 ≦ N ≦ 100 000，1 ≦ Q ≦ M ≦ 200 000，1 ≦ Ui ≦ N，

1 ≦ Vi ≦ N，Ui != Vi ，1 ≦ Rj ≦ M，Rj != Rk (1 ≦ j < k ≦ Q)。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int maxm=2e5+5;
pair<int,int> e[maxm];
vector<int> g[maxn],temp;
vector<pair<int,int>> ge[maxn];
int n,m,q,d[maxn],fa[maxn],qq[maxm],num,sz[maxn];
bool k[maxm],is[maxm];
int find(int x){
    if(fa[x]==x)return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
int add(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx==fy)return 0;
    bool px=(fx==find(1)),py=(fy==find(1));
    int cnt=0;
    if(px&&!py)cnt=sz[fy];
    if(!px&&py)cnt=sz[fx];
    fa[fx]=fy;
    sz[fy]+=sz[fx];
    return cnt;
}
void bfs(){
    queue<int> q;
    memset(d,-1,sizeof(d));
    d[1]=0;
    q.push(1);
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i];
            if(d[v]==-1)d[v]=d[u]+1,q.push(v);
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        e[i]={u,v};
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bfs();
    for(int i=1;i<=m;i++){
        int u=e[i].first,v=e[i].second;
        if(d[u]+1==d[v]||d[v]+1==d[u]){
            k[i]=1;
            ge[u].push_back({v,i});
            ge[v].push_back({u,i});
        }
    }
    for(int i=1;i<=q;i++){
        scanf("%d",&qq[i]);
        is[qq[i]]=1;
    }
    for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;
    for(int i=1;i<=m;i++)if(!is[i])add(e[i].first,e[i].second);
    for(int i=2;i<=n;i++)if(find(i)==find(1))num++;
    temp.push_back(n-1-num);
    for(int i=q;i>=2;i--){
        int id=qq[i];
        if(k[id])num+=add(e[id].first,e[id].second);
        temp.push_back(n-1-num);
    }
    reverse(temp.begin(),temp.end());
    for(int i=0;i<q;i++)printf("%d\n",temp[i]);
    return 0;
}

讨论操作