Fork me on GitHub

铁路运输

发表于 | | 阅读次数:
字数统计: 1,474

铁路运费 (train.pas/c/cpp)

吐槽：今天摸你赛好颓啊。。。

【问题描述】

  • 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 国的铁路路线信息和提价计划，输出每次满意度调查里存在不满市民的城市个数。

【输入】

  • 第一行为 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的运费。

【输出】

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

【输入输出样例1】

1
2
3
4
5
6
7
8
9
10
11
12
5 6 5
1 2
1 3
4 2
3 2
2 5
5 3
5
2
4
1
3
1
2
3
4
5
0
2
2
4
4

【输入输出样例2】

1
2
3
4
5
6
7
8
9
10
11
12
13
4 6 6
1 2
1 3
1 4
2 3
2 4
3 4
1
4
2
5
3
6
1
2
3
4
5
6
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）

题解。。。（膜拜hdhd）

由于当时我在颓。。。没仔细想啊我太弱了

把原图改为只有1到各点为最短路的图，于是改边权可变为删边（具体原理，用心体会）

于是最后查询时，若这条边的点入度为零就删点，因为此时这个点到1不是最短路，所以ans++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//丢个代码溜了呀，再次膜拜hdhd
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<queue>
#define ll long long
#define inf 0x3f3f3f3f
#define maxn 100005
using namespace std;
int N,M,Q;
int Last[maxn],Next[maxn<<2],End[maxn<<2],o=1;
int dis[maxn];
int belong[maxn<<1],id[maxn<<1];
int du[maxn];
vector<int>G[maxn];
bool del[maxn];
int ans;
queue<int>Qu;
void ins(int a,int b){
	End[++o]=b;
	Next[o]=Last[a];
	Last[a]=o;
}
void inss(int a,int b){
	ins(a,b),ins(b,a);
}
void Del(int u){
	if(del[u])return;
	del[u]=1;
	ans++;
	for(int i=0,v;i<G[u].size();++i){
		v=G[u][i];
		if(v<0)continue;
		--du[v];
		G[u][i]=-1;
		if(!du[v])Del(v);
	}
}
int main(){
	scanf("%d%d%d",&N,&M,&Q);
	int a,b;
	for(int i=1;i<=M;++i){
		scanf("%d%d",&a,&b),inss(a,b);
	}
	for(int i=2;i<=N;++i)dis[i]=inf;
	Qu.push(1);
	while(Qu.size()){
		int u=Qu.front();
		Qu.pop();
		for(int i=Last[u],v;i;i=Next[i]){
			v=End[i];
			if(dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;
				Qu.push(v);
			}
		}
	}
	for(int u=1;u<=N;++u){
		for(int i=Last[u],v;i;i=Next[i]){
			v=End[i];
			if(dis[v]==dis[u]+1){
				++du[v];
				belong[i>>1]=u;
				id[i>>1]=G[u].size();
				G[u].push_back(v);
			}
		}
	}
	int tmp;
	while(Q--){
		scanf("%d",&tmp);
		if(!belong[tmp]){//不在最短路中 
			printf("%d\n",ans);
			continue;
		}
		int u=belong[tmp],v=G[u][id[tmp]];
		if(v<0){//边删了 
			printf("%d\n",ans);
			continue;
		}
		G[u][id[tmp]]=-1;
		--du[v];
		if(!du[v])Del(v);//若入度为零就删点，此时这个点到1不是最短路即ans++ 
		printf("%d\n",ans);
	}
	return 0;
}
0%
``` ```