无向正权/非负权图

删边最短路

正权的无向图，删除一条边，问之后的最短路是多少。

例题：CF1163F Indecisive Taxi Fee

引理1：只有删除掉最短路上的边才可能导致删边最短路增大。

引理2：删边后的最短路一定是经过最短路一段前缀+中间的一些不在最短路的边+最短路一段后缀。

证明显然，不再赘述。

因此，我们可以设必须经过一个点的起点到终点的最短路经过最短路前缀几个点为 pre ，后缀几个点为 suf 。

如果存在多种选择随便选择一个即可。

引理3：prex≤sufx

证明也很简单，如果大于，说明起点到 x 或者 x 到终点至少有一条不是最短路。

这条引理是证明后面一条引理的关键，也是可以随便选择 pre 或者 suf 的原因，但是如果存在 0 边，就要选择最小的 pre ，最大的 suf ，这样才能保证正确性，同时如果是有向图这一结论也不成立。

引理4：设最短路 I ，删除边 (u,v)∈I ，设新最短路为 L ，存在一条路径 L 以及 (x,y)∈L 使得 L 是经过 (x,y) 的最短路。

这条引理是做法正确性的关键，来看看怎么证明：

为了方便，不妨设 I 为 1−n 连续编号的一条路径，其他点的编号大于 n ，设 L 的点序列为 x1,x2,…,xk 。

一定存在一个 L 满足 pre,suf 非严格递增，因为如果 prexi>prexi+1 ，那么可以直接走 1−xi+1 的最短路即可，suf 同理。

因此，现在就是证明存在 i 使得 prei≤u,sufi+1≥v=u+1 。

首先 x1=1,xk=n,prex1=1,surxk=n

如果 prei≤u,sufi+1≤u ，那么 prei+1≤u ，继续观察 i+1 ，如果同理如果都大于等于 v 则观察 i−1 。

不难看出，类似中值定理一样，一定存在一个 i 满足上述要求，经过 (xi,xi+1) 的其中一条最短路便是删边最短路，得证。

也就是说如果存在删边最短路，图中一定存在某条边，强制以某个方向经过这条边的最短路便是删边最短路。

因此预处理出每个点的 pre,suf ，暴力遍历每条边的两个方向的最短路即可求出其可能是最短路上哪些边的删边最短路，直接区间取min即可。

当然，如果离线可以差分加 multiset 。

具体可以看洛谷上这一道题目的题解，这里着重证明其正确性。

需要注意的是，如果有 0 边需要取最小的 pre ，最大的 suf ，否则可能导致引理 3 不正确，当然此题是正权，随便取就行了。

代码？没有，口胡罢了。洛谷的题解也不少了，应该够了。

删点最短路

正权图，删起终点以外的点。

不能直接套用删边最短路。

为什么？

因为有可能一个点的 pre=suf ，导致直接卡死，拆点又是有向图，不行。

因此，我们着重处理一个点 pre=suf 的情况。

先解释一下为什么，修改删点最短路中定理的描述，改成 $pre_xi的话，那么会有也只会有一个问题，中间会不会有点pre=suf=i$ ，仔细想想就知道。

那么，我们只需要针对最短路的每个点 i 把 pre=suf=i 的点提取出来，然后将相邻的 $prei$ 处理出到终点的最短路，相加统计贡献就行了。

时间复杂度依旧是带个 log 。

讨论一下 pre,suf 可不可以随机取的问题，最大最小能过，且在找 pre=suf=i 时这样的点一定与最短路的 i 相连，可以 BFS 找出。但是随机取的话没有零边（删边最短路部分就不行了），也行，只不过可能不能 BFS 找出了，毕竟随机的话不一定存在与最短路相连的路径了，可能需要预处理出每个 i 对应的点集才能保证时间复杂度正确，不过也不一定，没有具体实践卡过，例题部分去掉 min,max 也能过，只是单纯个人感觉罢了。不过出于保险起见我还是会打最大最小的，不怕一万就怕万一。

例题

2006. Kirill the Gardener @ Timus Online Judge

网格图的删点最短路。

直接套就行了，慢慢做，不要慌张。

不过去掉了 min,max 部分也能 AC ，说明有可能随机也可以直接 BFS 处理出 pre=suf 的点。

L 就是 pre ，R 就是 suf 。

时间复杂度：O(nmlog⁡nm)

空间复杂度：O(nm)

cpp
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#define NM 110000
using namespace std;
inline int mymin(int x,int y){return x<y?x:y;}
inline int mymax(int x,int y){return x>y?x:y;}
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
int n,m,nm;
char ss[NM];
struct node{
	int x,y;
	node(int xx=0,int yy=0){x=xx;y=yy;}
}list[NM],st,ed,pre[NM],ord[NM];int h1[NM],h2[NM],h[NM],head,tail,limit;
int fid[1100][1100];
inline int id(node x){return fid[x.x][x.y];}//1
inline bool pd(int x,int y){return x>=1 && y>=1 && x<=n && y<=m && ss[id(node(x,y))]=='.';}
int L[NM],R[NM];
bool v[NM];
void bfs(bool b1,bool b2){
	memset(h,0,sizeof(h));memset(pre,0,sizeof(pre));
	if(!b2)list[head=tail=1]=st,h[id(st)]=1;
	else list[head=tail=1]=ed,h[id(ed)]=1;
	while(head<=tail){
		node x=list[head++];
		for(int t=0;t<=3;t++){
			node y=node(x.x+dx[t],x.y+dy[t]);
			if(pd(y.x,y.y)){
				if(!h[id(y)]){
					list[++tail]=y;h[id(y)]=h[id(x)]+1;pre[id(y)]=x;
					if(b1){
						if(!v[id(y)]){
							if(!b2)L[id(y)]=L[id(x)];
							else R[id(y)]=R[id(x)];
						}
					}
				}
				else if(h[id(y)]==h[id(x)]+1){
					if(b1){
						if(!v[id(y)]){
							if(!b2)L[id(y)]=mymin(L[id(x)],L[id(y)]);
							else R[id(y)]=mymax(R[id(x)],R[id(y)]);
						}
					}
				}
			}
		}
	}
}
vector<int> add[NM],del[NM];
multiset<int> fuck;
int sta[NM],top;
int zans[NM];
int d1[NM],d2[NM],dd[NM];
inline bool operator>(node x,node y){return dd[id(x)]>dd[id(y)];}
priority_queue<node,vector<node>,greater<node> > smile;
void Pao(int now){
	while(!smile.empty()){
		node x=smile.top();smile.pop();
		for(int t=0;t<=3;t++){
			node y=node(x.x+dx[t],x.y+dy[t]);
			if(pd(y.x,y.y)==1 && h[id(y)]==now && !dd[id(y)]){
				dd[id(y)]=dd[id(x)]+1;
				smile.push(y);
			}
		}
	}
}
int check(int ttx,int tty){
	memset(h,0,sizeof(h));
	list[head=tail=1]=st,h[id(st)]=1;
	while(head<=tail){
		node x=list[head++];
		for(int t=0;t<=3;t++){
			node y=node(x.x+dx[t],x.y+dy[t]);
			if(pd(y.x,y.y) && !(y.x==ttx && y.y==tty) && !h[id(y)])list[++tail]=y,h[id(y)]=h[id(x)]+1;
		}
	}
	if(!h[id(ed)])return 999999999;
	else return h[id(ed)];
}
int main(){
	scanf("%d%d",&n,&m);nm=n*m;
	scanf("%d%d%d%d",&st.x,&st.y,&ed.x,&ed.y);
	for(int i=1;i<=n;i++)scanf("%s",ss+(i-1)*m+1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)fid[i][j]=(i-1)*m+j;
	}
	bfs(0,0);
	limit=h[id(ed)];
	node x=ed;
	while(h[id(x)]){//1'
		ord[h[id(x)]]=x;
		L[id(x)]=R[id(x)]=h[id(x)];
		v[id(x)]=1;
		x=pre[id(x)];
	}
	if(limit==2){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(ss[fid[i][j]]=='.' && !v[fid[i][j]]){
					printf("%d %d\n",i,j);
					return 0;
				}
			}
		}
	}
	bfs(1,0);memcpy(h1,h,sizeof(h));
	bfs(1,1);memcpy(h2,h,sizeof(h));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			node x=node(i,j);
			if(pd(i,j) && h1[id(x)]){//能够到达 
				for(int t=0;t<=3;t++){
					int tx=i+dx[t],ty=j+dy[t];
					if(pd(tx,ty) && h1[id(node(tx,ty))]){
						int ll=L[id(x)],rr=R[id(node(tx,ty))],val=h1[id(x)]+h2[id(node(tx,ty))];ll++;rr--;
						if(ll<=rr)add[ll].push_back(val),del[rr].push_back(val);
					}
				}
			}
		}
	}
	for(int i=2;i<limit;i++){
		for(int j=0;j<add[i].size();j++)fuck.insert(add[i][j]);
		if(fuck.empty())zans[i]=999999999;
		else zans[i]=(*fuck.begin());
		for(int j=0;j<del[i].size();j++)fuck.erase(fuck.find(del[i][j]));
	}
	memset(h,0,sizeof(h));
	for(int i=2;i<limit;i++){
		list[head=tail=0]=ord[i];h[id(ord[i])]=-1;
		while(head<=tail){
			node x=list[head++];
			for(int t=0;t<=3;t++){
				node y=node(x.x+dx[t],x.y+dy[t]);
				if(pd(y.x,y.y)==1 && L[id(y)]==R[id(y)] && L[id(y)]==i && !h[id(y)])h[id(y)]=i,list[++tail]=y;
			}
		}
		for(int j=1;j<=tail;j++){
			node x=list[j];dd[id(list[j])]=0;
			for(int t=0;t<=3;t++){
				node y=node(x.x+dx[t],x.y+dy[t]);
				if(pd(y.x,y.y)==1 && L[id(y)]<i){
					dd[id(y)]=h1[id(y)];smile.push(y);//2
				}
			}
		}
		Pao(i);for(int j=1;j<=tail;j++)d1[id(list[j])]=dd[id(list[j])],dd[id(list[j])]=0;
		for(int j=1;j<=tail;j++){
			node x=list[j];
			for(int t=0;t<=3;t++){
				node y=node(x.x+dx[t],x.y+dy[t]);
				if(pd(y.x,y.y)==1 && R[id(y)]>i){
					dd[id(y)]=h2[id(y)];smile.push(y);//2
				}
			}
		}
		Pao(i);for(int j=1;j<=tail;j++)d2[id(list[j])]=dd[id(list[j])],dd[id(list[j])]=0;
		for(int j=1;j<=tail;j++){
			if(d1[id(list[j])] && d2[id(list[j])])zans[i]=mymin(zans[i],d1[id(list[j])]+d2[id(list[j])]-1);
		}
	}
	int ans=0;node ansxy;
	for(int i=2;i<limit;i++){
		if(zans[i]>ans)ans=zans[i],ansxy=ord[i];
	}
	printf("%d %d\n",ansxy.x,ansxy.y);
	return 0;
}

说说我踩的3个坑。

  1. 如果路径长度为 2 ，随便找一个点堵上就行，对应是 WA9 。
  2. 代码中 1 的位置可以换成 (x.x-1)*m+x.y，不过要特判 id(0,0)=0 ，不然在 1′ 会访问负数下标导致错误，我曾经就疯狂 TLE8。
  3. 代码中 2 的位置一定要在加入堆之前赋值，我之前打反导致我一直以为 STL 的堆出问题了，顺便提一嘴，原来小根堆要重载大于号。

花了几天终于AC了，不容易不容易，感谢U群的各位了。

DAG

DAG的删点最短路

https://ac.nowcoder.com/acm/problem/14293?&headNav=acm

算是U群的意外收获吧。

其实发现一个事情，上面的关键结论其实对DAG也生效，单纯的对有环有向图不生效而已，删点最短路也是满足的，因此直接做就行了。

讨论里也有题解可以参考一下。

会了删边最短路的套路后这个就基本不难了，举一反三就行了。