首页 > 代码库 > 洛谷P1710地铁涨价
洛谷P1710地铁涨价
题目背景
本题开O2优化，请注意常数
题目描述
博艾市除了有海底高铁连接中国大陆、台湾与日本，市区里也有很成熟的轨道交通系统。我们可以认为博艾地铁系统是一个无向连通图。博艾有N个地铁站，同时有M小段地铁连接两个不同的站。
地铁计价方式很简单。从A站到B站，每经过一小段铁路（连接直接相邻的两个点的一条边），就要收取1博艾元。也就是说，从A站到B站，选择的路径不一样，要价也会不同。
我们认为凡华中学在1号地铁站。学生们通过地铁通勤，他们当然知道选择最短路来坐车的话，票价最便宜。
然而博艾地铁公司经营不善，一直亏损，于是他们打算提价。提价一次就是将一小段铁路原来收费1元改收2元。同一小段的铁路不会多次提价。他们打算提价Q次。
学生们知道，如果他们到学校的一条最短路径中的一小段提价了，可以改变路径，使总票价不变。然而随着一条一条的铁路被提价，当居住在某个站附近的学生发现，提价后，没有任何一种方案可以从家到学校的费用和初始费用相等时，就会不满。
现在地铁公司希望知道，对于每一次涨价，有多少个站，学生会因为涨价而不满呢？
输入输出格式
输入格式：第一行为三个整数N,M,Q。
接下来M行，每行2个整数ai,bi,表示第i条铁路连接的两个站。i表示铁路编号。
接下来Q行，每行一行整数rj，表示每次涨价的铁路编号。
输出格式：Q行。每行一个整数表示不满的车站数量。
输入输出样例
5 6 51 21 34 23 22 55 35241302244说明
【样例解释】
次数 车站2 车站3 车站4 车站5初始 1 1 2 21 1 1 2 22 1 2 2 33 1 2 2 34 2 2 3 35 2 2 4 3【数据范围】
对于20%的数据 N≤100, Q≤30
对于40%的数据 Q≤30
对于70%的数据 正确的输出结果中，不会有超过50种不一样的整数（数据范围剧透解法系列）
对于100%的数据 N≤100000, Q≤M≤200000
所有边权都是1，那么如果一条边原来在最短路上，边权增加以后，它就不再在原图的最短路上了。
于是问题转化成：求从最短路图中删边带来的影响
大概90%的删边问题都可以转化成：在一个所有需要删的边都删掉的图中，倒序加边
先求出原图最短路，然后把将要删的边都删掉。倒序加边，每次加边计算有多少个点到1的最短距离和原图上该点到1的最短距离相等。
之后答案求前缀和即可。
刚开始谜之30分，怒看题解。
当我发现我得代码和题解神似的时候，我的内心是欣喜的。
当我发现我WA是因为变量用混的时候，我的内心是崩溃的。
1 /*By SilverN*/ 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #include<algorithm> 7 #define LL long long 8 using namespace std; 9 const int mxn=200010; 10 int read(){ 11 int x=0,f=1;char ch=getchar(); 12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 14 return x*f; 15 } 16 int n,m,q; 17 struct mapp{ 18 int x,y; 19 }eg[mxn]; 20 struct edge{ 21 int v,nxt,id; 22 }e[mxn<<1]; 23 int hd[mxn],mct=0; 24 void add_edge(int u,int v,int id){ 25 e[++mct].v=v;e[mct].nxt=hd[u];e[mct].id=id;hd[u]=mct; 26 } 27 // 28 int qe[mxn];bool ban[mxn]; 29 int dis[mxn],mdis[mxn]; 30 int ans[mxn]; 31 int que[mxn];bool vis[mxn]; 32 void BFS(){ 33 int hed=0,tl=1,i,j; 34 que[++hed]=1;vis[1]=1; 35 dis[1]=1; 36 while(hed<=tl){ 37 int u=que[hed++]; 38 for(i=hd[u];i;i=e[i].nxt){ 39 int v=e[i].v; 40 if(vis[v])continue; 41 dis[v]=dis[u]+1; 42 vis[v]=1; 43 que[++tl]=v; 44 } 45 } 46 return; 47 } 48 int DFS(int u,int fa){ 49 int res=0; 50 for(int i=hd[u],v;i;i=e[i].nxt){ 51 v=e[i].v; 52 if(v==fa)continue; 53 if(dis[v]!=dis[u]+1 && mdis[v]==dis[u]+1){ 54 dis[v]=dis[u]+1; 55 res++; 56 res+=DFS(v,u); 57 } 58 } 59 return res; 60 } 61 void sol(){ 62 int i,j; 63 for(i=q;i;--i){ 64 int now=qe[i]; 65 int x=eg[now].x,y=eg[now].y; 66 add_edge(x,y,now); 67 add_edge(y,x,now); 68 if(dis[x]==mdis[x]&&dis[y]!=mdis[y]&&mdis[y]==dis[x]+1){ 69 dis[y]=dis[x]+1; 70 ans[i]=DFS(y,x)+1; 71 continue; 72 } 73 if(dis[y]==mdis[y]&&dis[x]!=mdis[x]&&mdis[x]==dis[y]+1){ 74 dis[x]=dis[y]+1; 75 ans[i]=DFS(x,y)+1; 76 } 77 } 78 return; 79 } 80 int main(){ 81 n=read();m=read();q=read(); 82 int i,j,u,v; 83 for(i=1;i<=m;++i){ 84 eg[i].x=read();eg[i].y=read(); 85 add_edge(eg[i].x,eg[i].y,i); 86 add_edge(eg[i].y,eg[i].x,i); 87 } 88 for(i=1;i<=q;++i)qe[i]=read(),ban[qe[i]]=1; 89 BFS(); 90 // 91 memcpy(mdis,dis,sizeof dis);//保存最短距离 92 memset(dis,0x3f,sizeof dis); 93 memset(vis,0,sizeof vis); 94 memset(e,0,sizeof e); 95 memset(hd,0,sizeof hd); 96 mct=0; 97 //reload 98 for(i=1;i<=m;++i){ 99 if(!ban[i]){100 add_edge(eg[i].x,eg[i].y,i);101 add_edge(eg[i].y,eg[i].x,i);102 }103 }104 dis[1]=1;105 BFS();106 sol();107 for(i=1;i<=q;++i){108 ans[i]+=ans[i-1];109 printf("%d\n",ans[i]);110 }111 return 0;112 }
洛谷P1710地铁涨价