OI题解 - 铁路票价(LOJ) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI题解 - 铁路票价(LOJ)

发表于 分类于 Valine：

一道关于删边的贪心问题

感觉自己想的时候很简单，不知道为什么其他人都没这么想，老师的正解也比较奇怪

# 题面

> LOJ

# 解析

- 一个联想

看到这样一种“只删边不加边，而且在当某一些边都被删除的时候会对答案造成影响”的题，我首先联想到的是 LCT 维护一般图连通性的问题：

给出一个无向图，进行删边加边操作，询问两点是否连通。

（因为是 LCT，也可以有加边 awa）我们考虑用 LCT 做。LCT 维护的是一棵树，但是这是一个图，可能有环。我们只能用 LCT 维护图上的一些边，使得图的连通性不变（其实就是维护图的一个生成森林）。

怎么做呢？可以离线 ！先处理出每条加入的边被删除的时间。

然后我们就在 LCT 上删边加边——

  1. 加边 $(u,v)$：如果 $u,v$ 本身不连通，直接加边；如果 $u,v$ 连通，那么加入 $(u,v)$ 后会形成环，于是我们找到形成的环上最早被删除的一条边，然后把它删掉，很像生成树算法中的破圈法。
  2. 删边：如果这条边在 LCT 里就删掉，不然就不管他。

为什么正确呢？考虑我们删去 LCT 上一条边 $(u,v)$ 的时候，在 LCT 上 $u,v$ 就不连通了，此时在图上一定也不连通——因为 LCT 维护了两点之间存在时间最长的一条路径，如果这条路径都断了，那其他路径也已经断了。

- 回到最短路

那么把 LCT 维护存在时间最长的路径的思想运用到这道题，其实就是维护每个节点 $u$ 到节点 $1$ 的存在时间最长的一条最短路。

那就很方便了——原本最短路 Dijkstra 只需要存 dis[u] 表示 $u$ 到 $1$ 的最短路，现在再加上一个 tim[u] 表示 $u$ 到 $1$ 的最短路中最晚被删除的一条是什么时候被删除（就是存在时间最长）。转移的时候以 dis[u] 为第一关键字，tim[u] 为第二关键字。

复杂度 $O(n\log n)$，离线。

要在线的话也可以 :) 不就是写个 LCT 嘛（算了）

# 源代码

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
/*Lucky_Glass*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5,M=2e5;

struct GRAPH{
	int head[N+3],to[M*2+3],nxt[M*2+3],id[M*2+3],ncnt;
	GRAPH(){ncnt=0;}
	void AddEdge(int u,int v,int i){
		int p=++ncnt,q=++ncnt;
		to[p]=v;nxt[p]=head[u];id[p]=i;head[u]=p;
		to[q]=u;nxt[q]=head[v];id[q]=i;head[v]=q;
	}
	int operator [](int id){return head[id];}
}Gr;

int n,m,t;
int mdi[M+3],ans[M+3];
bool fix[N+3];

struct DATA{
	int dis,tim,u;
	DATA(){}
	DATA(int _d,int _t,int _u):dis(_d),tim(_t),u(_u){}
}dat[N+3];
bool operator <(const DATA &A,const DATA &B){
	if(A.dis!=B.dis) return A.dis>B.dis;
	if(A.tim!=B.tim) return A.tim<B.tim;
	return A.u<B.u;
}

int Ri(){
	int a=0,c=getchar();
	while(c<'0' || '9'<c)
		c=getchar();
	while('0'<=c && c<='9'){
		a=(a<<1)+(a<<3)+c-'0';
		c=getchar();
	}
	return a;
}
void Dijkstra(){
	priority_queue< DATA > que;
	que.push(dat[1]=DATA(0,t+1,1));
	while(!que.empty()){
		int u=que.top().u;que.pop();
		if(fix[u]) continue;
		fix[u]=true;
		for(int it=Gr[u];it;it=Gr.nxt[it]){
			int v=Gr.to[it];
			if(fix[v]) continue;
			if(dat[v].dis<dat[u].dis+1) continue;
			if(dat[v].dis==dat[u].dis+1 && dat[v].tim>=min(mdi[Gr.id[it]],dat[u].tim)) continue;
			dat[v].dis=dat[u].dis+1;
			dat[v].tim=min(mdi[Gr.id[it]],dat[u].tim);
			que.push(dat[v]);
		}
	}
}
int main(){
	//freopen("price.in","r",stdin);
	//freopen("price.out","w",stdout);
	n=Ri();m=Ri();t=Ri();
	for(int i=1;i<=m;i++) Gr.AddEdge(Ri(),Ri(),i), mdi[i]=t+1;
	for(int i=1;i<=t;i++) mdi[Ri()]=i;
	for(int i=1;i<=n;i++) dat[i]=DATA(n+1,0,i);
	Dijkstra();
	for(int i=1;i<=n;i++) ans[dat[i].tim]++;
	for(int i=1;i<=t;i++) ans[i]+=ans[i-1];
	for(int i=1;i<=t;i++) printf("%d\n",ans[i]);
	return 0;
}

THE END

Thanks for reading!