12.图论1 最短路之dijkstra算法

图论

常见类型的图

二分图

判定：染色法。

性质：

• 可以二着色。
• 无奇圈。

BFS&DFS

树的直径模板

两遍dfs/bfs，证明时反证法的核心是用假设推出矛盾。

设1是一开始随机选的点，s是与其最远的点，证明s是直径的一端。

反证：假设s不是直径的一端，ss是直径的一端。

现在要做的就是证明ss是直径的一端是错误的，从而不存在s的反面的情况即可完成证明。

要证ss是直径的一端是错误的，那么要将ss所在的最长的径与直径比较，这里在证明时卡顿，要提升推理速度。

要将ss所在的最长的径与直径比较，就要讨论1和s所在的径与ss的全部情况。

如果全部情况都能证明ss是直径是错误的，那么就能完成证明。

分类讨论是证明的关键。

我们可以分为1在or不在ss所在的最长径上。

（1）1在。
（2）1不在。
2.1：1到s的径与ss的“直径”有公共部分。
2.2：无公共部分。

这样就讨论完了全部情况。

最短路（重点）

图概念

点：图论中的基本元素，表示多种意义。

边：点与点之间存在某种联系的桥梁。

本质：图可以表示不同点之间多对多的关系。

一个有用的公式：

点的度数之和=边数*2。（无向图）

特别地,在树中，点的度数之和=(n-1)*2。

运用：将点的度数之和与边数建立了联系。

一个在最短路问题中证明常常用到的实用工具：BFS生成树。（尤其是边权为1的无向图）

• bfs生成树可以在奇偶性相关的证明中利用层次关系证明（e.g.二分图两个性质互推）。
• bfs生成树也是边权为1的无向图的一个点的最短路径树，揭示了其他点到根的距离信息。

e.g.ABC281G

构造一张 $N$ 个点的无向连通图，边权都是 $1$。记图中 $1$ 到 $u$ 的最短路径长度为 $d_u$，你需要保证 max ⁡ { d 1 , d 2 , . . . , d N − 1 } \max\{d_1,d_2,...,d_{N-1}\} max{d1​,d2​,...,dN−1​} 严格小于 $d_N$。求构造方案数模 $M$ 的值，方案区分节点编号。

难点：将题目转化为构造bfs生成树数量，利用bfs生成树的层次关系计数。

问题转换为：找bfs生成树，其中1在第一层，n在最下面一层。

这是一个计数问题，可以用dp+组合数学解决。

$d{p}_{i,j}$表示除去1和n，一共放了i个点，最后一层j个的方案数。

省略掉bfs生成树层次这个冗余信息，不将它放到状态，而用已经安排i个点划分阶段同样是个难点。

转移：与bfs生成树上一层的方案数+这一层之间的方案数+上一阶段的方案数。

细节：mi初始化不要算少了。

#include<cstdio>
#define int long long
using namespace std;
const int maxn=510;
int mi[maxn*maxn],n,m,dp[maxn][maxn],ans,C[maxn][maxn],mii[maxn][maxn];
signed main(){
	scanf("%lld%lld",&n,&m);
	mi[0]=1;
	for(int i=1;i<=n*n;i++) mi[i]=2*mi[i-1]%m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			mii[i][0]=1;
			mii[i][j]=(mi[i]-1+m)%m*mii[i][j-1]%m;
		}
	C[0][0]=1;
	for(int i=1;i<=n;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%m;
	}
	for(int i=1;i<=n-2;i++) dp[i][i]=mi[i*(i-1)/2]*C[n-2][i]%m;
	for(int i=2;i<=n-2;i++)
		for(int j=1;j<i;j++){
			for(int k=1,t=1;k<=i-j;k++){
				dp[i][j]=(dp[i][j]%m+dp[i-j][k]%m*mii[k][j]%m*C[n-2-(i-j)][j]%m)%m;
			}
			dp[i][j]=dp[i][j]%m*mi[j*(j-1)/2]%m;
		}
	for(int j=1;j<=n;j++)
		ans=(ans +dp[n-2][j]%m*(mi[j]-1+m)%m)%m;
	printf("%lld",ans);
	return 0;
}

无向图生成树

方法：并查集。

应用：如仅需表示无向图的连通性，可以减省信息。

Dijkstra

应用一：在最短路（bfs）途中记录额外信息。

e.g.最短路计数

加一个cnt数组记录。

应用二：双参数最短路。

P1：HDU3790

长度和花费两个参数，都是加和，优先长度，长度一样选花费小的。

P2: Travel in Desert

温度和长度两个参数，温度取max，优先温度低的，温度一样选长度小的。

本质区别：有无后效性。

P1的加和不管后面怎么加，都不会影响当前一步的选择，直接改堆的比较函数即可。

P2的取温度中的最大值当前的温度收到后面温度的影响，当前贪温度小的可能后面有一条非常热的边导致前功尽弃，而且还不能保证长度小。

解决方法是先把有后效性的元素在全局解决，再解决无后效性的长度。

解决温度：

• 法1：先sort然后从小到大加边并查集查连通性，在并查集的新图上跑长度的最短路。
• 法2：二分最大的温度，跑log次最短路，跑最短路时只跑温度<=最大温度的边。

启示：有后效性的问题和无后效性的问题同时要求解决，优先在全局中先解决有后效性的问题，后解决无后效性的问题。

小trick：解决全局的有后效性的问题通常可以利用贪心，或者二分答案（有单调性）

应用三：反跑最短路。

花费非常数

知道边的属性和终点的信息，求起点。

反跑最短路即可。

值得一提的是，最短路的边权不仅可以事先就确定，利用跑到某个结点的信息再确定也行，e.g.边权是到某点的最短路百分之几。

总之可以在它更新其他点时知道边权即可。

应用四：最短路径树

圣诞树

每个节点有重量W，每条边有价格C。

需要找到一颗代价最小的树。

每条边的子孙重量之和乘上它的价格是这条边的代价。

一颗树的代价是所有边代价之和。

trick：树中边的问题往往要转移到点上解决。

综合：打车问题

给定无向图。某个点可以花费用$c_i$，去距离不超过$t_i$的点。

和前面带温度的双参最短路有点像，最后答案问的是最小花费。

但是是否能到达只解决这个问题之前就需要解决的问题。

先跑距离最短路，再将能花费ci到的点重新构图。

多个参数带来多个问题的题，要解他就像剥洋葱，分清问题之前的包含关系，先后顺序，一个图对应一个参数带来的问题解决即可。

应用五：许多dp方程可以用最短路优化，状态看成点。（dp方程满足最短路松弛的式子）

CF1005F

打印k个最短路径树。

对于一棵树，可以看成除了根以外每个点与它的父亲连一条边。

回溯法搜索即可。

构图技巧练习

同余最短路

题目特点：

• 数据范围（值域）巨大，与位数相关或者大到O(n)都实现不了。
• 以某个数的同余类为点（不同的集合/概念）。

Small multiple

输入k，找k的某个倍数，这个数各位数字之和最小。

将每个同余类看成点，为每个同余类求最小花费。

用两种边可以表示各个同余类之间全部的关系：

• 边权为1的边表示加1（i->(i+1)%k）。
• 边权为0的边表示乘10（i->(10*i)%k）。

计算时，ans=从1到0的最短路+1；

证明可以证上下界。

东华中学2022普及组T4：电话号码

与同余相关的题，但是是bfs。

0,1,2,…,n-1组成的自然数中，能被m整除的最小数。

0为根，每一层代表一位数，第一层有0,1…n-1。

由于要求数的大小最小，所以定义vis[0…m-1]（同余类问题的共通之处）表示mod m的余数是否访问过，取第一个访问过的为答案，由于bfs可以保证是最优解。

实现时给bfs生成树上的点标号，记录前驱编号，每一步填的是什么，用于输出。

假设到点x的余数为r，则新的点y的余数为(r*10+t)%m，t是枚举0~n-1的这步填的数。

时间复杂度$O(mn)$。

#include<cstdio>
#include<stack>
using namespace std;
const int maxn=1010;
bool vis[maxn];
struct node{
	int r,val,pre;
}a[maxn];
int n,m,st,ed;
stack<int> s;
int main(){
	freopen("phone.in","r",stdin);
	freopen("phone.out","w",stdout);
	scanf("%d%d",&n,&m);
	while(st<=ed){
		for(int i=st==0?1:0;i<n;i++)
			if(!vis[(a[st].r*10+i)%m]){
				vis[(a[st].r*10+i)%m]=1,ed++;
				a[ed].r=(a[st].r*10+i)%m,a[ed].val=i,a[ed].pre=st;
				if(!a[ed].r){
					s.push(a[ed].val);
					for(int j=a[ed].pre;j;j=a[j].pre)
						s.push(a[j].val);
					while(!s.empty()){
						printf("%d",s.top());s.pop();
					}
					return 0;
				}
			}
		st++;
	}
	return 0;
}

类比上面的电话号码和Small multiple。

我们可以得到一个同样可以用同余最短路解决的问题：

0,1,2,…,n-1组成的自然数中，能被m整除的各位之和相加最小的数。

相当于给Small mutiple加个一个各位组成的数不超过n的限制。

解决方案是对于同余类x，我们建边的时候枚举0~n-1的t，向点(x*10+t)%m加边权为t的边即可。

难点：保证数的组成，每走一步加数字t的边之前都要先*10。

跳楼机

给定h，x，y，z输出1~h中所有由a，b，c加起来组成的数的个数。

$1\le h\le 2^{63}-1，1\le x,y,z\le 10^5$

数据范围巨大的货币系统，显然不能直接判断每个数能否被组成。

计数肯定要分类计，而x，y，z的大小可以在$O(nlogn)$的时间下解决。

数据范围特别大的题考虑用数学优化。

观察可以发现，对于1~h中的数，到了某一个数x，所有>=x的数都可以组成。

从同余的角度考虑，假设有0~x-1的同余类，那么只通过y和z相加得到的某个数t，t所处的同余类中所有数都可以通过t+kx得到。

那么我们找到通过y，z相加得到的x每个同余类的最小数，就可以算出有哪些数可以得到了，分类统计了所有数。

具体的：

• 第t个同余类向(t+y)%x建一条边权为y的边。
• 第t个同余类向(t+z)%x建一条边权为z的边。

难点：h范围巨大，无法判断每一个数是否可以得到。

分类计数是这题的核心思想。

和上面的small multiple一样，都是运用了某个数的同余类作为点构图，其他可以在同余类中用于转移的信息作为边，按同余类分类是这类问题的核心思想。

我们类比的想一个同样需要数学的题，给定巨大的h，a数组，问h中有几个数可以由a数组中不同元素相乘得到（1a[]…）。

h巨大，我们也用数学进行优化。

a[i]作为某个数的因数，哪些1~h的数有因数a[i]，直接h/a[i]即可。

有些是公倍数的数会被重复计算。

用容斥原理解决。

ans=n/奇数个数的gcd+n/偶数个数的gcd。

例子，h=1000，a[]={2,3,5,7}。()表示gcd

ans=h/2+h/3+h/5+h/7-h/(2,3)-h/(3,5)-h/(5,7)-h/(2,5)-h/(2,7)-h/(3,7)+h/(2,3,5)+h/(2,5,7)+h/(3,5,7)-h/(2,3,5,7)

定理：$\left(\genfrac{}{}{0ex}{}{n}{1}\right)-\left(\genfrac{}{}{0ex}{}{n}{2}\right)+\left(\genfrac{}{}{0ex}{}{n}{3}\right)-\left(\genfrac{}{}{0ex}{}{n}{4}\right)+...=1$。

引理：$\left(\genfrac{}{}{0ex}{}{n}{1}\right)+\left(\genfrac{}{}{0ex}{}{n}{3}\right)+\left(\genfrac{}{}{0ex}{}{n}{5}\right)+...=\left(\genfrac{}{}{0ex}{}{n}{0}\right)+\left(\genfrac{}{}{0ex}{}{n}{2}\right)+\left(\genfrac{}{}{0ex}{}{n}{4}\right)+...$

证明引理：

分类讨论n的奇偶性：

• n为奇数，易证。
• n为偶数，利用$\left(\genfrac{}{}{0ex}{}{n}{m}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{m}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{m-1}\right)$（可以用杨辉三角理解，也可以代数证明）证明即可。

根据引理易证定理。

实现上，多个数的gcd:

• gcd(a,b,c,d)=gcd(a,gcd(b,gcd(c,d)))。

但是这是一个指数阶的劣质算法。

用同余最短路也可以解，到第x个同余类的距离为dis[x]（代表一个数字的大小）,那么枚举t，t是a数组中的某个元素，x到（dis[x]*t）%m连一条边长为dis[x]*t-dis[x]的边。

虽然不一定实用，但是这里可以让我们联系到前面非常花费数的百分率做边权的启示：边权也可以是根据到某点的最短路结合参数算出的数，只要在用到边权更新之前能算出边权即可。

其他构图问题：

Xanadu

给定n*n的01矩阵，第i行左边第一个1的位置为j，则存在一条i->j的有向边。
现在可以删掉一些1，每删一个花费1块钱，从起点到终点最少花费多少钱。

给定了每行的i到每列的点的一些关系，根据图的定义，我们可以用边表示不同点之间的关系，并且用边权表示花费，对于第i行，所有为1的点都可能成为i可以到的点。

做法，第i行向第j个1连边权j-1的边，跑最短路。

Strong Defence

给定无向图，起点终点，将边分成尽量多的子集，使得任意两个子集不相交，删掉任意一个子集图不连通。

观察可以发现，如果尽量多，那么bfs生成树（最短路径树）中每一层连接下一层的边集一定划分到同一个集合中，才能最多。

答案就是有最短路长度d个数个集合。

证明：

反证：

• 假如比d个集合少，设最短路中第i条边没有单独成集合，如果让它单独成集合，那么也能保证删掉任意集合图不连通，每条边在一个集合，比原答案多一个集合，即原答案不是最优的。
• 假如比d个集合还多，那么一定可以找到一个集合不包含d中任意一条边，因为每条边最多在一个集合中。（鸽舍原理）

总上，最多分成d个集合并且满足要求。

本质上这题还是最短路径树的应用。

trick：最短路生成树的层级之间的边集是保证图连通的最小充分条件。

实现时注意：t不一定是离s最短的点，即不一定是bfs生成树最下面一层。

所以分层时t的层级之间的按上述规则分，其余的随便分。

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=410;
int dis[maxn],n,m,s,t,cnt=1,head[maxn];
bool vis[maxn];
queue<int>q;
vector<int>vv[maxn*maxn<<1],tmp;
struct edge{
	int to,nxt,u;
}e[maxn*maxn<<1],ed[maxn*maxn<<1];
void add(int u,int v){
	e[cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt++;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++){
		int u,v;scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
		ed[i].u=u,ed[i].to=v;
	}
	q.push(s),vis[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(!vis[v]){
				vis[v]=1,dis[v]=dis[u]+1;
				q.push(v);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,dis[i]);
	for(int i=1;i<=m;i++){
		int u=ed[i].u,v=ed[i].to;
		if(dis[u]!=dis[v]){
			if(max(dis[v],dis[u])<=dis[t]) vv[max(dis[v],dis[u])].push_back(i);
			else tmp.push_back(i);
		}
		else tmp.push_back(i);
	}
	printf("%d\n",dis[t]);
	for(int i=1;i<=dis[t];i++){
		if(i==1){
			printf("%d ",vv[i].size()+tmp.size());
			for(auto j:vv[i]) printf("%d ",j);
			for(auto j:tmp) printf("%d ",j);
			printf("\n");
			continue;
		}
		printf("%d ",vv[i].size());
		for(auto j:vv[i])
			printf("%d ",j);
		printf("\n");
	}
	return 0;
}

Shortest Path

• 给定无向图，n<=3000,m<=20000。
• 给定k个三元组，k<=10000。
• 不能按顺序访问三元组中的元素。
• 求1到n的最短路。

难点：要表示三点关系。

传统的图中一条边只能表示两点关系，那么我们化边为点，第一条边表示(x,y)的关系，第二条边表示(y,z)的关系，那么再用一条边（化边为点的图中）就能表示原图三点的关系。

trick：表示三点关系可以化边为点重新构图。

本质上还是利用了图用边表示两点关系的定义。

为了方便和避免MLE我们可以直接在原图上实现。

实现时，我们还是可以在原图上跑最短路，把边加入优先队列，由于有顺序的存在，我们先将无向边变成双向有向边(便于确定一条边最终到哪个点，即使三元组不存在顺序也最好这样做)。

dis[i]表示最后一条边是e[i]并且落在e[i]到的点的最短路。

先排序预处理出no[i][c]表示第i条边不能更新到c点。

注意：一条边可能对应多个c，一个c只能对应一条边。

一开始先将所有从1出发的点加入优先队列，更新时根据第i条边到的点结合no数组判断是否将当前准备更新的边加入队列即可。

#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=3010;
const int maxm=2e4+10;
int n,m,head[maxm<<1],cnt=1,k,dis[maxm<<1],pre[maxm<<1];
bool no[maxm<<1][maxn],vis[maxm<<1];
queue<int>q;
struct node{
	int a,b,c;
}jin[maxm*5];
struct edge{
	int u,v,nxt,id;
}e[maxm<<1],ed[maxm<<1];
void add(int u,int v){
	e[cnt].u=u,e[cnt].v=v,e[cnt].nxt=head[u];head[u]=cnt++;
}
bool cmp(edge x,edge y){
	if(x.u==y.u) return x.v<y.v;
	return x.u<y.u;
}
bool cmpp(node x,node y){
	if(x.a==y.a){
		if(x.b==y.b) return x.c<y.c;
		return x.b<y.b;
	}
	return x.a<y.a;
}
void print(int x){
	if(x==0) return;
	print(pre[x]);
	printf("%d ",e[x].v);
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++){
		int u,v;scanf("%d%d",&u,&v);
		add(u,v);ed[i].id=cnt-1;
		add(v,u);ed[i+m].id=cnt-1;
		ed[i].u=u,ed[i].v=v;
		ed[i+m].u=v,ed[i+m].v=u;
	}
	for(int i=1;i<=k;i++) scanf("%d%d%d",&jin[i].a,&jin[i].b,&jin[i].c);
	sort(ed+1,ed+cnt,cmp);
	sort(jin+1,jin+1+k,cmpp);
	int now=1;
	for(int i=1;i<=k;i++){
		while((ed[now].u<jin[i].a||(ed[now].u==jin[i].a&&ed[now].v<jin[i].b))&&now<=2*m) now++;
		if(ed[now].u==jin[i].a&&ed[now].v==jin[i].b&&now<=2*m){
			no[ed[now].id][jin[i].c]=1;
			int t=ed[now].id;
		}
	}
	memset(dis,0x7f,sizeof(dis));
	for(int i=head[1];i;i=e[i].nxt)
		q.push(i),dis[i]=1,vis[i]=1;
	while(!q.empty()){
		int now=q.front();
        q.pop();
		int v=e[now].v;
		for(int i=head[v];i;i=e[i].nxt){
			int vv=e[i].v;
			if(no[now][vv]||vis[i]) continue;
			 vis[i]=1,dis[i]=dis[now]+1,pre[i]=now;
			 q.push(i);
		} 
	}
	int ans=0x7f7f7f7f,t=-1;
	for(int i=1;i<cnt;i++)
		if(e[i].v==n)
			if(ans>dis[i]){
				ans=dis[i];
				t=i;
			}
	if(ans==0x7f7f7f7f){
		printf("-1");
		return 0;
	}
	printf("%d\n",ans);
	printf("1 ");print(t);
	return 0;
}

earth hour

给定n<=200个圆（圆心+半径），实际上是n个灯，开灯为圆关灯为点，求连通三点最少需要经过几个点。

难点：

• 简化问题，观察分析出有用的点必然是开着的。
• 解决在图中经过最少的点使得三个点连通的问题。

解决方法：

构图：将两个有公共部分的圆连边（权为1）。一个点包含在一个圆内但是不开灯的点没必要经过，对于连通其他点没有价值，并且没有必要经过这个点。

解决经过最少的点使得三点连通的问题：首先三个点连通一定无环，否则去掉环会更优。

那么三个点肯定在一颗树内，根据树的性质n个点n-1条边，树中包含最少点即为经过最少边。

问题转换为找一个点d使得他到三点距离之和最小，先跑n次最短路预处理全源最短路即可。

核心考点还是简化问题（被一条边连着的两点一定是都开着的），构图，树的性质，最短路。

一道有相似之处却截然不同的题：沙滩防御。

给定n<=1000个点的圆心和0~m<=800个列找到一个最小的使得m个列被完全覆盖的所有半径中最大的半径r。

最小瓶颈路的模板题，这里的半径只是图中的最大边，而和上道题的连通两个开着的灯的边意义完全不同。

Okabe and City

给定n*m的方格，$n,m,k<=10^4$，求(1,1)到(n,m)的最小花费。
给定k个原来就亮着灯的格子，无时无刻都得站在亮灯的格子上。
保证(1,1)亮灯但不保证（n,m）亮灯。
可以进行多次如下操作：

• 站在某个本来就亮灯的格子上可以花费一块钱指定任意一行或列亮灯。
• 在亮灯的格子上可以花费0块钱直接走到上下左右的四个格子上。

方法1：根据分析我们的一个原来就亮的点那么他上下左右和他自己所在的行列都可以直接花费1到达。

据此可以构图，最坏被卡成时空都是平方，MLE。

但是可以通过不建图，在每次跑spfa的时候来一遍1~k的循环，考虑可以走向哪个点。

时间其实是假的，但是可以卡过这题，算是考场求生的奇技淫巧了：建图MLE时跑spfa，通过循环考虑到哪个点，由于spfa可能在小常数*n的时间复杂度跑完最短路，有时可以卡过一些题。

正解：

由于方法1的图边数太多，导致MLE，所以我们可以用加中间节点或是虚拟点的trick来减少边数。

考虑一个原来就亮灯的点他使用1块钱使得某行或列亮灯一定只会使得自己的行列和上下左右四个行列亮灯，一共只有6种关系，所以我们将行和列也当做点，构图，大大减少了边数。

具体的：点x是原来就亮灯的点。

• x上下左右四个点如果原来就亮灯，直接连一条边权为0的边。
• x的6个有关系的行列向x连权为0的边，x向他们连边权为1的边。（讨论x是花钱点亮某行某列还是从被点亮的某行某列到的点的两种情况，而避免了x到某行或列再讨论这个行列能连到哪些其他点，这样增加了写代码的难度）这种讨论一个点分别处于不同情况的思想值得学习

难点：将行列也当做点达到减少原图边数的效果。

关键还是抓一个点能分几种情况到其他位置的信息，选少情况的构图。

new island

给定简单无向连通图，n<=200个点。
删掉第i条边获得$2^i$的收益，在满足删掉去掉一些边并保证现在图的各点最短路不超过原图两倍，最大化收益。

我们先考虑要删掉哪些边，$2^i$是给我们的提示，观察样例我们也不难发现，先删最大的边。因为如果不把最大的删掉，哪怕把其余的全删掉都没有删最大的收益大。

$2^{+}...+2^{n-1}=2^n-1$

然后考虑原来的条件怎么简化。

简化问题：通过画图观察，删掉某一条边之后，最难满足的就是这条边原来连的两个点，他们原来的最短路是1，现在要求删掉边之后最短路长度为2。进一步思考，如果删掉的这条边是其他某两个点的最短路，那么他们这段原来在最短路上长度为1的边现在有长度为2的代替了，那么这一段肯定合法了，我们最低满足的限度就是在那两个点所有段都至少有长度为2的可以代替。

所以我们可以得到：如果删掉某条边使得初始图中有边相连的两个点都有长度<=2的边。

现在要思考如何实现：如何判断任意时刻某两点是否有长度为2或1的边且能表示哪些边存在，哪些不存在。

定义G[x][y]

• 0表示本来无边
• 1表示现在仍有边
• -1表示最初有边但是删掉了（要与最初的最短路比较，所以必须将本来就无边和删掉的区分开）。

定义：num[x][y]表示存在长度为2的路的个数。

由于长度为2的边不一定和最短路有关，所以我们容易惯性想到记录删掉边后会影响哪些的最短路行不通。

num数组十分巧妙，一方面容易记录，另一方面删边之后容易更新。

现在考虑删掉(x,y)这条边，看看哪些点的num会被减少。

由于（x，y）长度已经为1，要被影响点z一定和x或者y现在有边相连，如果a,b两点都和x，y无关那么肯定影响不到他们，他们之中一点离x或者y的距离至少为三，画图不难证明。
，

• 如果G[x][z]==1那么num[y,z]–,num[z,y]–
• 如果G[y][z]==1那么num[x,z]–,num[z,x]–

并且删掉(x,y)要将G[x,y]=G[y,z]=-1;

还要判断哪些边能删，首先，x，y必须有长度为2的路，其次要考虑会被影响num的z。如果z与x，y是初始有边在前面删掉了，那么一定要保证他们之间至少还有1条长度为2的路径，如果要减少num的有他们，那么一定不能删。

以下情况不能删。

• num[x,y]<1
• G[x,z]==1&&G[y,z]==-1&&num[y,z]<=1
• G[y,z]==1&&G[x,z]==-1&&num[x,z]<=1

难点：简化问题，和想到G和num数组。

比较常规的是贪心和最后的分类讨论，画图都不难想到。

核心考点：观察简化问题的思想，对于动态更新的量记录的信息要精准，不然可能要额外浪费时间（num数组），分类讨论哪些被影响。

知识点：最短路，bfs生成树（讨论被影响的点和求num），贪心。

Tax

给出一个 $n$ 个点 $m$ 条边的无向图，经过一个点的代价是进入和离开这个点的两条边的边权的较大值，求从起点 $1$ 到点 $n$ 的最小代价。起点的代价是离开起点的边的边权，终点的代价是进入终点的边的边权。

本质上一个点的花费是两条边之间的关系。

化无向图为有向图，再化边为点，重新构图。

化为有向图？

• 有向边的终点可以与原图一一对应，从而证明构图的正确性。
• 而无向图无法确定最终在哪一端。

下面称一开始输入的图为原图，化边为点之后的图为新图。

暴力加边用新图点权（其实就是原图边权）取max加边容易得到。

但是这种做法TLE了，边数太大。

我们考虑加虚点减少边数。

假设点u（原图中某点）的所有边（包括进入u和从u出去的边）的边边权各不相同。

如果原来有相同的边权，我们可以看成两个是不同的，假装有次序。

对应u点所有的边的不同权值，构建虚点。

其中虚点 $(u,w)$ 表示关于u的边权值为w的原图中的正反边的中转站。

可以看成这个虚点对应原图的一条边，并且每个虚点连有两个新图真点和一个虚点。

建边及各边含义：

对于u，每个虚点之间差分建边，以满足取最大值的要求。

对于原图进入 $u$ 权为 $w$ 的边我们想这个虚点连边权为 $w$ 的有向边，它的意义是原来可以通过进入u这个方向的边可以通过w的花费到达u，并且借助这个虚点连接的其他虚点可以到达从u出发的所有边。

对于原图从 $u$ 出的边权为 $w$，蓄电向这条边连权为 $0$ 的边，表示别的进入u的边可以通过这条边出去。

新图中点的个数大约为：$8\ast 10^5$。
边的个数约为：$32\ast 10^5$。

用dijkstra算法可以AC。

#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#include<map>
#include<utility>
#include<cstring>
#define int long long 
#define mkp(x,y) make_pair(x,y) 
using namespace std;
const int maxn=8e5+10;
int head[100010],cnt=2,n,m,tot,cntt=1,h[maxn],dis[maxn];
map<pair<int,int>,int>mp;
struct edge{
	int nxt,w,to,id;
}e[400010],ee[24000010];
struct ed{
	int to,w,id;
	ed(int to_,int w_,int id_){
		to=to_,w=w_,id=id_; 
	}
	ed(){}
};
vector<ed>G[100010];
bool operator <(ed x,ed y){
	return x.w<y.w;
}
inline void add(int u,int v,int w){
	e[cnt].to=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt++;
} 
inline void ad(int u,int v,int w){
	ee[cntt].to=v,ee[cntt].w=w,ee[cntt].nxt=h[u],h[u]=cntt++;
}
struct node{
	int u,w;
	node(int u_,int w_){
		u=u_,w=w_;
	}
	node(){}
};
bool operator<(node x,node y){
	return x.w>y.w;
}
priority_queue<node>q;
bool vis[maxn];
inline int read(){
	int flag=1,x=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') (ch=='-')?flag=-1:flag=flag,ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*flag;
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=m;++i){
		int u,v,w;u=read(),v=read(),w=read();
		add(u,v,w),G[u].push_back(ed(v,w,cnt-1));
		add(v,u,w),G[v].push_back(ed(u,w,cnt-1));
	}
	tot=2*m+2;
	for(int i=1;i<=n;++i){
		if(G[i].size()==0) continue;//实现上这里有个坑
		sort(G[i].begin(),G[i].end());
		tot++;
		mp[mkp(i,G[i][0].w)]=tot;
		for(int j=1;j<G[i].size();++j){
			++tot;
			mp[mkp(i,G[i][j].w)]=tot;
			ad(tot-1,tot,G[i][j].w-G[i][j-1].w);
			ad(tot,tot-1,0);
		}
	}
	int s=++tot,t=++tot;
	for(int i=1;i<=n;++i)
		for(int j=head[i];j;j=e[j].nxt){
			int u=i,v=e[j].to,w=e[j].w;
			ad(mp[mkp(u,w)],j,0);
			ad(j,mp[mkp(v,w)],w);
			if(u==1) ad(s,j,w);
			if(v==n) ad(j,t,w);
		}
	memset(dis,0x3f,sizeof(dis));
	q.push(node(s,0)),dis[s]=0;
	while(!q.empty()){
		node now=q.top();
		q.pop();
		int u=now.u;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=h[u];i;i=ee[i].nxt){
			int v=ee[i].to;
			if(dis[v]>dis[u]+ee[i].w){
				dis[v]=dis[u]+ee[i].w;
				q.push(node(v,dis[v]));
			}
		}
	}
	printf("%lld",dis[t]);
	return 0;
}

trick:对于取最大、小值的情况可以差分建边实现，并且配合对应某个值的虚点可以使得边数较少

trick：考虑每个点的花费是否为边与边的关系，如果是考虑化边为点重新构图。

这题的难点是差分建边从而使的一条进入u边能很好的利用u所有的出边。

还可以对于u的每一条出边差分建边，然后正反边连原来边权的双向边从而使得当中一点充当另一点的上述的虚点。原理就是进入u的边要利用的一定是出u的边，而这条边的反向边正是出u的边，扫u的所有边差分建边恰好能满足。

[ABC232G] Modulo Shortest Path

题目描述：给定有$n<=2\ast 10^5$个点的完全图，和模数$m$，每个点有$A_i,B_i$两个属性，边$(u,v)$的边权是$(A_u+B_v)\mathrm{mod}m$。

解法：

取模即与余数相关，边权肯定不超过m，因此可以将所有状态用0…m-1的m的同余系表示。
涉及到余数相关的（包括因数、倍数、取模）是同余最短路的一大特征。
边权由两个部分组成，即包含起点u又包含终点v，直接构图时平方级别的TLE。
因此要优化构图边数，所有取模的公共特征是边权不超过，那么我们不妨选一个点进行分割点，在分割点之前走mod m意义下的$A_u$步，在分割点之后走mod m意义下的$B_v$ 步，那么对于每个边权，都可以通过mod m的余数上的变化来完整的表示。那么为了方便计算，不妨选0来作为分界点，建立点0…，m-1，对于每个点i，建立他到$(0-A_i)$作为i出发的前半部分花费（此时i充当的是u），点$B_i$连向i作为到点i的后半部分的花费（此时i充当的是v）即可表示所有花费。
保留环上用到的点恰好2n个，边数也是2n可以AC。0…m-1之前的相邻的点互相转移的代价是1。
这里优化复杂度利用的重复条件是到点i的代价恒为$B_i$，利用同余关系很容易表示这个代价。

考虑利用重叠优化有以下两个角度：

• u到的边有哪些可以利用重叠减少的。
• 到v的边有哪些可以利用重叠减少的。

arc061C

如果乘客只乘坐同一公司的铁路，他只需要花费一元，但如果更换其他公司的铁路需要再花一元。当然，如果你要再换回原来的公司，你还是要花一元。

同样是边与边的关系，用上述做法就是将边权相同的正、反、邻边都连上权值为0的边，然后将每一个原图中的点都建一个虚点，将权不同的边中任意一边向虚点连权值为1的入边和权值为0的出边。

这题其实核心的是连通性，更好的做法是，利用并查集将同一个连通性分量中的点建立虚点，所有分量中的点与虚点连权为0.5的双向边。

实现时将边权*2最后再/2即可。

#include<cstdio>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=1e5+2e5+10;
int head[100010],cnt=1,fa[100010],n,m,tot,cl[100010],pre=1,f[200010],h[maxn],cntt=1,dis[maxn];
bool vis[maxn];
vector<int>v;
queue<int>q;
map<int,int>mp;
struct edge{
	int to,nxt,id,u,w;
	edge(int u_,int to_,int id_,int w_){
		u=u_,to=to_,id=id_,w=w_;
	}
	edge(){}
}e[400010],ed[200000],ee[800010];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void Union(int x,int y){
	x=find(x),y=find(y);
	if(x==y) return;
	fa[x]=y;
}
void add(int u,int v,int id){
	e[cnt].to=v,e[cnt].nxt=head[u],e[cnt].id=id,head[u]=cnt++;
}
void ad(int u,int v){
	ee[cntt].to=v,ee[cntt].nxt=h[u],h[u]=cntt++;
}
bool cmp(edge x,edge y){
	return x.w<y.w;
}
int hx(int x){
	if(mp.find(x)==mp.end()) mp[x]=++tot;
	return mp[x];
}
void wk(int now){
	for(auto i:v)
		cl[i]=hx(find(i));
	for(int i=pre;i<=now;i++){
		int u=ed[i].u,v=ed[i].to,id=ed[i].id;
		if(find(u)==find(v))
			f[id]=cl[u];
	}
}
void cle(){
	for(auto i:v) cl[i]=0,fa[i]=i;
	v.clear(),mp.clear();
}
int main(){
	scanf("%d%d",&n,&m);
	tot=n;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		add(u,v,i),add(v,u,i);
		ed[i]=edge(u,v,i,w);
	}
	sort(ed+1,ed+1+m,cmp);
	for(int i=1;i<=m+1;i++){
		if(i!=1&&ed[i].w!=ed[i-1].w){
			wk(i-1);
			cle();
			pre=i;
		}
		Union(ed[i].u,ed[i].to);
		v.push_back(ed[i].u),v.push_back(ed[i].to);
	}
	for(int i=1;i<=n;i++)
		for(int j=head[i];j;j=e[j].nxt){
			ad(i,f[e[j].id]),ad(f[e[j].id],i);
		}
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0,q.push(1);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=h[u];i;i=ee[i].nxt){
			int v=ee[i].to;
			if(dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;
				q.push(v);
			}
		}
	}
	printf("%d",dis[n]==0x3f3f3f3f?-1:dis[n]/2);
} 

Low cost air travel

题意翻译：
很多航空公司都会出售一种联票，要求从头坐，上飞机时上缴机票，可以在中途任何一站下飞机。比如，假设你有一张“城市1->城市2->城市3”的联票，你不能用来只从城市2飞到城市3（因为必须从头坐），也不能先从城市1飞到城市2再用其他票飞到其他城市玩，回到城市22后再用原来的机票飞到城市3（因为机票已经上缴）。

和上题有点像，联票就向与连通性相关的。

但是却截然不同。

我们要解决的问题是满足某个游玩顺序的最短路，而直接求起点终点的不会满足题意，为了玩一些城市可能绕远。

分别求每两个城市之间最短路，也不一定是最优解，有可能在某一个城市的联票多往后走几个城市能用更优惠的票。

这题的难点就在于解决按行程表跑最短路的问题。

由于要求每个点作为第几个到，中间还可能有非必要的点。

那么对于每个点，我们加一个维度，代表这个点是作为第几个到的点。

如果一张联票中有可以不连续个满足行程单的点那么是可以将后面的点作为当前枚举的点的下个到的点的状态的。

在新图中跑最短路即可。

这题的核心是每个点都可以作为第任意个到的点，但是能通过1，1走到的才是合法的。

并且构图的时候还用了贪心思想，能在这条线到的不放到下一条线到。

虽然这题看似和连通性相关，但是第几个到（状态）是关键。

代码细节有点多自己的还没调好，先放个题解的。

#include <algorithm>
#include  <iostream>
#include   <cstdlib>
#include   <cstring>
#include    <cstdio>
#include    <string>
#include    <vector>
#include     <cmath>
#include     <ctime>
#include     <queue>
#include       <map>
#include       <set>

using namespace std;

#define ull unsigned long long
#define pii pair<int, int>
#define uint unsigned int
#define mii map<int, int>
#define lbd lower_bound
#define ubd upper_bound
#define INF 0x3f3f3f3f
#define IINF 0x3f3f3f3f3f3f3f3fLL
#define DEF 0x8f8f8f8f
#define DDEF 0x8f8f8f8f8f8f8f8fLL
#define vi vector<int>
#define ll long long
#define mp make_pair
#define pb push_back
#define re register
#define il inline

#define N 10000

struct Edge {
  int next, from, to, w, id;
}e[2000000];

int ticketCnt, routeCnt, nodeCnt, cityCnt;
int price[250], cities[250];
vi tickets[250];
map<pii, int> nodeId;
mii cityId;
pii originNode[N+5];
int head[N+5], eid;
int d[N+5], pre[N+5];
bool inq[N+5];
int stk[N+5], tp;
queue<int> q;

void addEdge(int u, int v, int w, int id) {
  e[++eid] = Edge{head[u], u, v, w, id};
  head[u] = eid;
}

void spfa() {
  memset(d, 0x3f, sizeof d);
  memset(inq, 0, sizeof inq);
  memset(pre, 0, sizeof pre);
  int S = nodeId[mp(1, cities[1])];
  d[S] = 0;
  q.push(S);
  while(!q.empty()) {
    int u = q.front(); q.pop();
    inq[u] = 0;
    for(int i = head[u]; i; i = e[i].next) {
      int v = e[i].to, w = e[i].w;
      if(d[v] > d[u]+w) {
        d[v] = d[u]+w;
        pre[v] = i;
        if(!inq[v]) inq[v] = 1, q.push(v);
      }
    }
  }
}

void mark(int u) {
  if(!pre[u]) return ;
  stk[++tp] = e[pre[u]].id;
  mark(e[pre[u]].from);
}

int main() {
  int kase = 0;
  while(~scanf("%d", &ticketCnt) && ticketCnt) {
    ++kase;
    nodeCnt = cityCnt = 0;
    nodeId.clear();
    cityId.clear();
    for(int i = 1, cnt; i <= ticketCnt; ++i) {
      scanf("%d%d", &price[i], &cnt);
      tickets[i].clear();
      for(int j = 1, x; j <= cnt; ++j) {
        scanf("%d", &x);
        if(!cityId.count(x)) cityId[x] = ++cityCnt;
        tickets[i].pb(cityId[x]);
      }
    }
    scanf("%d", &routeCnt);
    for(int t = 1, len; t <= routeCnt; ++t) {
      memset(head, 0, sizeof head);
      eid = 0;
      scanf("%d", &len);
      for(int c = 1; c <= len; ++c) {
        scanf("%d", &cities[c]);
        if(!cityId.count(cities[c])) cityId[cities[c]] = ++cityCnt;
        cities[c] = cityId[cities[c]];
      }
      for(int ticket = 1; ticket <= ticketCnt; ++ticket) {
        for(int i = cities[1] == tickets[ticket][0]; i <= len; ++i) {
          int cnt = i;
          pii cur = mp(i, tickets[ticket][0]);
          if(!nodeId.count(cur)) nodeId[cur] = ++nodeCnt, originNode[nodeCnt] = cur;
          for(int j = 1; j < tickets[ticket].size(); ++j) {
            if(cnt+1 <= len && cities[cnt+1] == tickets[ticket][j]) cnt++;
            pii newState = mp(cnt, tickets[ticket][j]);
            if(!nodeId.count(newState)) nodeId[newState] = ++nodeCnt, originNode[nodeCnt] = newState;
            addEdge(nodeId[cur], nodeId[newState], price[ticket], ticket);
          }
        }
      }
      spfa();
      printf("Case %d, Trip %d: Cost = %d\n", kase, t, d[nodeId[mp(len, cities[len])]]);
      printf("  Tickets used: ");
      tp = 0;
      mark(nodeId[mp(len, cities[len])]);
      for(int i = tp; i > 1; --i) printf("%d ", stk[i]);
      printf("%d\n", stk[1]);
    }
  }
  return 0;
}

Recover path

给定无向图G（$m,n<=10^5$）。给定k个点，求一条路径包含这些点，是其中两个端点直之间的最短路，保证存在。

根据最短路的最优子结构性质，可以推出从k中任意找一点，跑最短路，最远的且是k中的一定是一个端点。

若最短路没有最优子结构，那么可以将较劣质的子结构改成更优的从而和最短路矛盾。

trick：最短路具有最优子结构性质，即路中经过的任意两点都是最短路。

然后加下来确定了两个端点考虑如何输出路径。

这个路径一定是包含最多个k的路径。

我们可以在其中一个端点的最短路径树（bfs生成树）上做树形dp，或者将最短路径树重新构图跑拓扑。

trick:找最短路如果有额外限制实际上可以看成在最短路径树上做树形dp

细节有点多，先贴题解代码，自己的还没调好。

#include <stdio.h>
#include <iostream>
#include<queue>
#include <string.h>
#include <algorithm>
#define maxn 200009
using namespace std;
typedef pair<int,int>pii;
int head[maxn],nxt[maxn],point[maxn],value[maxn],now=0;
int n,m,maxx=-1,po,dist[maxn],x,y,z,k,v[maxn],dp[maxn],egz[maxn];
int an=0,pp[maxn],final[maxn],oo=0;
int num[maxn],route[maxn];

void add(int x,int y,int v,int zz)/*456465*/
{
    nxt[++now]=head[x];
    head[x]=now;
    point[now]=y;
    value[now]=v;
    num[now]=zz;
}
struct cmp
{
    bool operator()(pii a,pii b)
    {
        return a.first>b.first;
    }
};
void dijkstra(int s)
{
    memset(dist,-1,sizeof(dist));
    dist[s]=0;
    priority_queue<pii,vector<pii>,cmp>q;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        pii u=q.top();
        q.pop();
        if(u.first>dist[u.second])continue;
        for(int i=head[u.second];i!=0;i=nxt[i])
        {
            int k=point[i];
            if(dist[u.second]+value[i]<dist[k] || dist[k]==-1)
            {
                dist[k]=dist[u.second]+value[i];
                q.push(make_pair(dist[k],k));
            }
        }
    }
}
int dfs(int s)
{
    if(dp[s]!=-1)return dp[s];
    int ans=0;
    for(int i=head[s];i!=0;i=nxt[i])
    {
        int u=point[i];
        if(dist[u]!=dist[s]+value[i])continue;
        int val=dfs(u);
        if(val>ans)
        {
            ans=val;
            pp[s]=u;
            route[s]=num[i];
            if(val==k-1)break;
        }
    }
    return dp[s]=ans+(egz[s]==1?1:0);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z,i);
        add(y,x,z,i);
    }
    scanf("%d",&k);
    for(int i=1;i<=k;i++){scanf("%d",&v[i]);egz[v[i]]=1;}
    dijkstra(v[1]);
    for(int i=1;i<=k;i++)if(dist[v[i]]>maxx)
    {
        maxx=dist[v[i]];
        po=v[i];
    }
    dijkstra(po);
    memset(dp,-1,sizeof(dp));
    dfs(po);
    an=po;
    while(pp[an]!=0)
    {
        final[++oo]=route[an];
        an=pp[an];
    }
    printf("%d\n",oo);
    for(int i=1;i<=oo-1;i++)printf("%d ",final[i]);
    printf("%d",final[oo]);
    return 0;
}

wandering queen

暴力拆8个点建八个方向的边$O(64mn)$会T。

于是考虑状态与方向无关，|—/这四种即可。

于是可以优化成$O(16mn)$可以通过。

更快的是将上下左右四个连通分量作为点，这样点数和边数更少了，但是本质上和直接存n*m个点四个方向是一样的。

由于老题需要卡常，先不卡了。

#include<cstdio>
#include<queue>
#include<algorithm>
#include<map>
#include<cstring>
using namespace std;
const int maxn=1e3+1;
const int dx[]={-1,0,1,1,1};
const int dy[]={-1,1,0,1,-1};
int fa[maxn*maxn],n,m,dis[maxn*maxn*4],tot,tott,a[maxn][maxn],G[maxn][maxn],d[maxn][maxn][5],head[maxn*maxn*4],cnt=1,rk[maxn*maxn*4];
bool vis[maxn*maxn*4];
struct node{
	int x,y;
	node(int x_,int y_){
		x=x_,y=y_;
	}
	node(){}
}S,T,b[maxn*maxn];
map<int,int>mp;
queue<int>q;
int insert(int x){
	if(mp.find(x)==mp.end()) mp[x]=++tott;
	return mp[x];
}
struct edge{
	int to,nxt;
}e[16*maxn*maxn];
void add(int u,int v){
	e[cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt++;
}
char str[maxn][maxn];
/*
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void Union(int x,int y){
	x=find(x),y=find(y);
	if(x==y) return;
	if(rk[x]>rk[y]) fa[y]=x;
	else if(rk[x]<rk[y]) fa[x]=y;
	else rk[y]++,fa[x]=y;

}
void w1(){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(G[i][j-1]&&G[i][j])
				Union(a[i][j-1],a[i][j]);
	for(int i=1;i<=tot;i++){
		int x=b[i].x,y=b[i].y;
		if(!G[x][y]) continue;
		d[x][y][1]=insert(find(i));
	}
	mp.clear();
	for(int i=1;i<=tot;i++) fa[i]=i,rk[i]=0;
}
void w2(){
	for(int j=1;j<=m;j++)
		for(int i=1;i<=n;i++)
			if(G[i-1][j]&&G[i][j])
				Union(a[i-1][j],a[i][j]);
	for(int i=1;i<=tot;i++){				
		int x=b[i].x,y=b[i].y;
		if(!G[x][y]) continue;
		d[x][y][2]=insert(find(i));
	}
	mp.clear();
	for(int i=1;i<=tot;i++) fa[i]=i,rk[i]=0;
}
void w3(){
	for(int j=1;j<=m;j++){
		int x=1,y=j;
		while(x<n&&y>1){
			x++,y--;
			if((G[x-1][y+1]||y+1>m)&&G[x][y])
				Union(a[x-1][y+1],a[x][y]);
		}
	}
	for(int i=2;i<=n;i++){
		int x=i,y=m;
		while(x<n&&y>1){
			x++,y--;
			if((G[x-1][y+1]||y+1>m)&&G[x][y])
				Union(a[x-1][y+1],a[x][y]);
		}
	}
	for(int i=1;i<=tot;i++){				
		int x=b[i].x,y=b[i].y;
		if(!G[x][y]) continue;
		d[x][y][3]=insert(find(i));
	}
	mp.clear();
	for(int i=1;i<=tot;i++) fa[i]=i,rk[i]=0;	
}
void w4(){
	for(int j=1;j<=m;j++){
		int x=1,y=j;
		while(x<n&&y<m){
			x++,y++;
			if(G[x-1][y-1]&&G[x][y])
				Union(a[x-1][y-1],a[x][y]);
		}
	}
	for(int i=2;i<=n;i++){
		int x=i,y=1;
		while(x<n&&y<m){
			x++,y++;
			if(G[x-1][y-1]&&G[x][y])
				Union(a[x-1][y-1],a[x][y]);
		}
	}
	for(int i=1;i<=tot;i++){				
		int x=b[i].x,y=b[i].y;
		if(!G[x][y]) continue;
		d[x][y][4]=insert(find(i));
	}
	mp.clear();
	for(int i=1;i<=tot;i++) fa[i]=i,rk[i]=0;
}*/
int main(){
	int tt;
	scanf("%d",&tt);
	while(tt--){
		cnt=1;
		for(int i=1;i<=tott;i++) head[i]=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%s",(str[i]+1));
		}
		tot=tott=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				G[i][j]=(str[i][j]=='X')?0:1;
				if(str[i][j]=='S') S=node(i,j);
				if(str[i][j]=='F') T=node(i,j);
				d[i][j][1]=d[i][j][2]=d[i][j][3]=d[i][j][4]=0;
			}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				if(!G[i][j]) continue;
				for(int t=1;t<=4;t++){
					if(!d[i][j][t]) d[i][j][t]=++tott;
					int nx=i+dx[t],ny=j+dy[t];
					if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&G[nx][ny]){
						d[nx][ny][t]=d[i][j][t];
					}
				} 
			}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				if(!G[i][j]) continue;
				for(int k=1;k<=4;k++)
					for(int kk=k+1;kk<=4;kk++){
						int x=d[i][j][k],y=d[i][j][kk];
						add(x,y),add(y,x);
					}
			}
		for(int i=1;i<=tott;i++) dis[i]=0x3f3f3f3f,vis[i]=0;
		for(int i=1;i<=4;i++){
			int x=d[S.x][S.y][i];
			vis[x]=1,dis[x]=1,q.push(x);
		}
		int ans=0x3f3f3f3f;
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int i=head[u];i;i=e[i].nxt){
				int v=e[i].to;
				if(!vis[v]&&dis[v]>dis[u]+1){
					dis[v]=dis[u]+1;
					q.push(v);
				}
			}
		}
		for(int i=1;i<=4;i++){
			int x=d[T.x][T.y][i];
			ans=min(ans,dis[x]);
		}
		printf("%d\n",ans==0x3f3f3f3f?-1:ans);
	}
	return 0;
}

用dp扫连通分量可以比并查集快一点。

Jzzhu and Cities

题意简述 $n$个点，$m$条带权边的无向图，另外还有$k$条特殊边，每条边连接$1$和$i$。

问最多可以删除这$k$条边中的多少条，使得每个点到$1$的最短距离不变。

数据范围：

$1\le u_i,v_i,s_i\le n\le 10^5$

$1\le k\le 10^5$

$1\le m\le 3\times 10^5$

$1\le x_i,y_i\le 10^5$

转换成以1为根的最短路径树，统计在k中的边是必要的的个数。

不用真的减数，令ct[i]为上一步可以有几个u以最短的长度到i。

然后对每个k分类讨论一下：

• $y_i>di{s}_i$ 这条特殊边无用，对最短路没影响直接删掉。
• $y_{[}i]==di{s}_i$
  • 如果有别的非特殊边就能以最短路到i那么这条边没用
  • 如果多条特殊边以最短路到i且不存在不走特殊边到i是最短路，就留一条。

第二种情况实现时将ct–，看最后是否为0即可。

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring> 
#define int long long
using namespace std;
const int maxn=8e5+10;
int head[100010],n,m,k,ans,cnt=1,dis[100010],ct[100010];
bool vis[100010];
struct node{
	int v,w;
	node(int u_,int w_){
		v=u_,w=w_;
	}
	node(){} 
}a[100010];
bool operator<(node x,node y){
	return x.w>y.w;
}
struct edge{
	int to,nxt,w;
}e[maxn];
void add(int u,int v,int w){
	e[cnt].to=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt++;
}
priority_queue<node>q;
signed main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=m;i++){
		int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
		add(u,v,w),add(v,u,w);
	}
	for(int i=1;i<=k;i++){
		int s,w;scanf("%lld%lld",&s,&w);
		a[i]=node(s,w);
		add(1,s,w),add(s,1,w);
	}
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0,q.push(node(1,0));
	while(!q.empty()){
		node now=q.top();
		q.pop();
		int u=now.v;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(dis[v]>dis[u]+e[i].w){
				dis[v]=dis[u]+e[i].w;
				ct[v]=1;
				q.push(node(v,dis[v]));
			}
			else if(dis[v]==dis[u]+e[i].w)
				ct[v]++;
		}
	}
	for(int i=1;i<=k;i++){
		if(a[i].w==dis[a[i].v]){
			ct[a[i].v]--;
		}
	}
	for(int i=1;i<=k;i++){
		if(a[i].w==dis[a[i].v]&&ct[a[i].v]==0){
			ans++;
			ct[a[i].v]++;
		}
	}
	printf("%lld",k-ans);
}

注意讨论重边的情况。

Edge Deletion

给一个nn个点,mm条边的无向简单带权连通图, 要求删边至最多剩余kk条边.

定义"好点"是指删边后, 1号节点到它的最短路长度仍然等于原图最短路长度的节点.

最大化删边后的好点个数.

和上题非常类似，只是把条件和要求调换了。

还是最短路径树的运用，如果在最短路径树上的边能留则留。文章来源地址https://www.toymoban.com/news/detail-828332.html

#include<cstdio>
#include<cstdlib> 
#include<queue>
#include<cstring>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
const int maxn=3e5+10;
vector<int>ans;
int head[maxn],cnt=1,dis[maxn],n,m,k;
bool vis[maxn];
struct edge{
	int to,nxt,w,id;
}e[maxn<<1];
struct node{
	int u,w;
	node(int u_,int w_){
		u=u_,w=w_;
	}
	node(){}
};
bool operator<(node x,node y){
	return x.w>y.w;
}
priority_queue<node>q;
void add(int u,int v,int w,int id){
	e[cnt].to=v,e[cnt].nxt=head[u],e[cnt].w=w,e[cnt].id=id,head[u]=cnt++;
}
void dfs(int u){
	if(ans.size()==k) return;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(dis[v]!=dis[u]+e[i].w||vis[v]) continue;
		vis[v]=1;
		ans.push_back(e[i].id);
		if(ans.size()==k) return;
		dfs(v);
		if(ans.size()==k) return;
	}
}
signed main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=m;i++){
		int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
		add(u,v,w,i),add(v,u,w,i);
	}
	memset(dis,0x3f,sizeof(dis));
	q.push(node(1,0)),dis[1]=0;
	while(!q.empty()){
		node now=q.top();
		q.pop();
		int u=now.u;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(dis[v]>dis[u]+e[i].w){
				dis[v]=dis[u]+e[i].w;
				q.push(node(v,dis[v]));
			}
		}
	}
	memset(vis,0,sizeof(vis));
	vis[1]=1;
	dfs(1);
	int t=ans.size();//细节
	printf("%lld\n",t);
	for(auto i:ans) printf("%lld ",i);
	return 0;
}

到了这里，关于12.图论1 最短路之dijkstra算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！