发布时间：2024-04-27

最短路与DFS

P5764 [CQOI2005] 新年好

题意

一张图，从源点1出发，需要拜访五个点，求最短路 $1 \leq N \leq 50000$ $1 leq M \leq 100000$

思路

五个点按照不同的顺序走，会有120种走法
预处理出五个点加上源点1的单源最短路，暴力枚举即可
本题卡spfa，需要堆优化的dijkstra

cpp

int n,m,S[10];
vector<PII> adj[N];
int dis[10][N];
bool st[N];
void spfa(int be){
	priority_queue<PII,vector<PII>,greater<PII>> q; 
	q.push({0,S[be]});
	memset(dis[be],0x3f,sizeof dis[be]);
	memset(st,0,sizeof st);
	dis[be][S[be]]=0;
	while(!q.empty()){
		auto [h,u]=q.top();
		q.pop();
		if(st[u])continue;
		st[u]=1;
		for(auto [v,c]:adj[u]){
			if(dis[be][v]>dis[be][u]+c){
				dis[be][v]=dis[be][u]+c;
				if(!st[v])q.push({dis[be][v],v});
			}

		}
	}
}
int ans=1e9;
bool vis[10];
int a[10];
int cnt;
void dfs(int x){
	if(x>5){
		int last=0;
		int sum=0;
		for(int i=1;i<=5;i++){
			sum+=dis[last][S[a[i]]];
			last=a[i];
		}
		cnt++;
		ans=min(ans,sum);
		return;
	}
	for(int i=1;i<=5;i++){
		if(!vis[i]){
			vis[i]=1;
			a[x]=i;
			dfs(x+1);
			vis[i]=0;
			a[x]=0;
		}
	}
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=5;i++)cin>>S[i];
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	S[0]=1;
	for(int i=0;i<=5;i++)spfa(i);
	dfs(1);
	cout<<ans<<"\n";
}

最短路与二分

P1948 [USACO08JAN] Telephone Lines S

题意

需要在1和N之间建立道路连通，每条道路有一个花费值l，
建筑公司可以免费建k条路，最终花费为道路上除那k条外的花费最大的那条路
$1 \leq N \leq 1000$
$1 \leq M \leq 10000$
$1 \leq l \leq 1000000$

思路

显然可以二分
对于大于mid的边，边权为1
小于等于mid的边，边权为0
判断dis[N]<=k

cpp

int n,m,k;
vector<PII> adj[N];
int dis[N];
bool vis[N];
bool check(int mid){
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	priority_queue<PII,vector<PII>,greater<PII>> q;
	dis[1]=0;
	q.push({0,1});
	while(!q.empty()){
		auto [H,u]=q.top();
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto [v,c]:adj[u]){
			c=c>mid?1:0;
			if(dis[v]>dis[u]+c){
				dis[v]=dis[u]+c;
				if(!vis[v])q.push({dis[v],v});
			}
		}
	}
	return dis[n]<=k;
}
void solve(){
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	int l=0,r=1000000;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	if(check(l))cout<<l<<"\n";
	else cout<<"-1\n";
}

最短路与拓扑排序

P3008 [USACO11JAN] Roads and Planes G

题意

n个点，有R条普通道路(双向)，P条航线(单向)，保证航线两个点不会有普通道路，给定源点S,求到每个点的最短路
普通道路无负权，航线有负权 $1 \leq N \leq 25000$
$1 \leq R,P \leq 50000$

思路

有多个联通块，连通块内部跑dijk
对于连通块与连通块之间跑拓扑序
拓扑序遍历到当前连通块时，对内部点跑dijk
- 当更新的v与u在同一块时直接更新
- 否则，v所在块入度减1，减为0时加入拓扑队列

cpp

int n,R,P,S,idx;
int id[N],in[N];
vector<int> block[N];
vector<PLL> adj[N];
LL dis[N];
bool vis[N];
queue<int> q;
void dfs(int u,int bid){
	id[u]=bid;
	block[bid].push_back(u);
	for(auto [v,c]:adj[u]){
		if(!id[v])dfs(v,bid);
	}
}
void dijk(int x){
	priority_queue<PLL,vector<PLL>,greater<PLL>> heap;
	for(auto it:block[x])heap.push({dis[it],it});
	while(!heap.empty()){
		auto [H,u]=heap.top();
		heap.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto [v,c]:adj[u]){
			if(dis[v]>dis[u]+c){
				dis[v]=dis[u]+c;
				if(!vis[v]&&id[u]==id[v])heap.push({dis[v],v});
			}
			if(id[u]!=id[v]&&--in[id[v]]==0)q.push(id[v]);
		}
	}
}
void topsort(){
	memset(dis,0x3f,sizeof dis);
	dis[S]=0;
	for(int i=1;i<=idx;i++){
		if(!in[i])q.push(i);
	}
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		dijk(u);
	}
}
void solve(){
	cin>>n>>R>>P>>S;
	for(int i=1;i<=R;i++){
		int u,v,w;
		cin>>u>>v>>w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	for(int i=1;i<=n;i++){
		if(!id[i])dfs(i,++idx);
	}
	for(int i=1;i<=P;i++){
		int u,v,w;
		cin>>u>>v>>w;
		adj[u].push_back({v,w});
		in[id[v]]++;
	}
	topsort();
	for(int i=1;i<=n;i++){
		if(dis[i]>INF/2)cout<<"NO PATH\n";
		else cout<<dis[i]<<"\n";
	}
}

最短路与dp

该类问题一般用于解决有环的dp问题，且会在过程中取min或max 一般使用spfa

P1073 [NOIP2009 提高组] 最优贸易

题意

给定N个点，有有向边和无向边
每个点有一个权值，表示一件物品卖出和买入的价格
求从1-N的路中，买入并卖出能获取的最大利润(大于0)

思路

对于一个点k，先求从1-k的最小价格，k-N的最大价格，则利润为二者差值
可以用spfa求这两个值

cpp

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
const int N=100010;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
int n,m,a[N];
vector<vector<int>> adj(N+1),adj_r(N+1);
int dmin[N],dmax[N];
bool st[N];
void spfa(int dis[],vector<vector<int>> &g,int op){
	queue<int> q;
	if(op==0){
		memset(dis,0x3f,sizeof dmin);
		dis[1]=a[1];
		q.push(1);
		st[1]=1;
	}
	else{
		memset(dis,-0x3f,sizeof dmax);
		dis[n]=a[n];
		q.push(n);
		st[n]=1;
	}
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		st[u]=0;
		for(auto v:g[u]){
			if((op==0&&dis[v]>min(dis[u],a[v]))||(op==1&&dis[v]<max(dis[u],a[v]))){
				if(!op)dis[v]=min(dis[u],a[v]);
				else dis[v]=max(dis[u],a[v]);
				if(!st[v]){
					q.push(v);
					st[v]=1;
				}
			}
		}
	}
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++){
		int u,v,c;
		cin>>u>>v>>c;
		adj[u].push_back(v);
		adj_r[v].push_back(u);
		if(c==2)adj[v].push_back(u),adj_r[u].push_back(v);
	}
	spfa(dmin,adj,0);
	spfa(dmax,adj_r,1);
	int ans=0;
	for(int i=1;i<=n;i++)ans=max(ans,dmax[i]-dmin[i]);
	cout<<ans<<"\n";
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}

最短路计数问题

法1：BFS

如果边权均为1，则直接bfs即可，因为此时bfs即为拓扑序

法2：Dijkstra

如果边权非负，可以使用Dijkstra，顺带记录最短路数即可，也是自带拓扑序

法3：SPFA

如果边权有负，则不能使用上述两种方法
spfa没有拓扑序，不能直接计数
因此需要先跑最短路
然后再跑一次最短路，如果当前更新值等于最短路的值，说明当前边是其中一条最短路的边，将该边保留
最终会建成一颗最短路树
在该最短路树跑拓扑排序计数即可

floyd的应用

求最短路

传递闭包

有向图内，如果i能到达k，k能到达j，则i能到达j

模板

cpp

int adj[N][N],n;
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)cin>>adj[i][j];
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(adj[i][k]&&adj[k][j])adj[i][j]=1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)cout<<adj[i][j]<<" \n"[j==n];
	}
}

P1347 排序

题意

给定26个字母的大小关系

询问是否矛盾，是否唯一确定，不唯一

思路

很明显可以用拓扑序来求，但是题目还要求求出第几次确定整体关系，若是唯一则要输出序列，因此直接拓扑并不好求
可以使用floyd，每次插入跑一次，本质上就是传递闭包
- 如果此时有 $dis_{i,i}=1$ ，说明矛盾，直接返回
- 如果二者有确定关系则有 $dis_{i,j}==1||dis_{j,i}==1$ $d i s_{i, j} == 1∣∣ d i s_{j, i} == 1$
  - 如果唯一确定了，则每次找出一个最小值并标记，输出
- 否则答案不唯一

cpp

int adj[N][N],g[N][N],n,m;
bool st[N];
void floyd(){
	memcpy(g,adj,sizeof g);
	for(int k=0;k<n;k++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(g[i][k]&&g[k][j])g[i][j]=1;
			}
		}
	}
}
int check(){
	for(int i=0;i<n;i++){
		if(g[i][i])return 2;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<i;j++){
			if(!g[i][j]&&!g[j][i])return 0;
		}
	}
	return 1;
}
char get(){
	for(int i=0;i<n;i++){
		if(st[i])continue;
		bool flag=0;
		for(int j=0;j<n;j++){
			if(i==j||st[j])continue;
			if(g[j][i]){
				flag=1;
				break;
			}
		}
		if(!flag){
			st[i]=1;
			return 'A'+i;
		}
	}
	return 0;
}
void solve(){
	cin>>n>>m;
	vector<array<char,3>> OP;
	for(int i=1;i<=m;i++){
		char x,op,y;
		cin>>x>>op>>y;
		OP.push_back({x,op,y});
	}
	int type=0,cnt=0;
	for(auto [x,op,y]:OP){
		adj[x-'A'][y-'A']=1;
		cnt++;
		floyd();
		type=check();
		if(type==2){
			cout<<"Inconsistency found after "<<cnt<<" relations.\n";
			return;
		}
		if(type==1){
			cout<<"Sorted sequence determined after "<<cnt<<" relations: ";
			for(int i=1;i<=n;i++)cout<<get();
			cout<<".\n";
			return;
		}
	}
	cout<<"Sorted sequence cannot be determined.\n";
}

最小环问题

使用floyd不重不漏地计算最小环规则
按照每个环中编号的最大值来算
首先第一重循环枚举到k，之前更新的最短路中编号必定小于k
因此枚举小于k的编号i,j,然后此时k即为环的最大编号
- 因为i,k与k,j均为一条边
- i,j的最短路路径上编号小于k
然后更新答案即可
至于路径，可以每次记录分界点pos

cpp

int n,m;
int adj[N][N],d[N][N],pos[N][N];
int path[N],cnt;
void get_path(int i,int j){
	if(pos[i][j]==0)return;
	get_path(i,pos[i][j]);
	path[cnt++]=pos[i][j];
	get_path(pos[i][j],j);
}
void solve(){
	cin>>n>>m;
	memset(adj,0x3f,sizeof adj);
	for(int i=1;i<=n;i++)adj[i][i]=0;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		adj[u][v]=adj[v][u]=min(adj[u][v],w);
	}
	memcpy(d,adj,sizeof d);
	LL ans=INF;
	for(int k=1;k<=n+1;k++){
		for(int i=1;i<k;i++){
			for(int j=i+1;j<k;j++){
				if((LL)d[i][j]+adj[i][k]+adj[k][j]<ans){
					ans=(LL)d[i][j]+adj[i][k]+adj[k][j];
					cnt=0;
					path[cnt++]=k;
					path[cnt++]=i;
					get_path(i,j);
					path[cnt++]=j;
				}
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(d[i][j]>d[i][k]+d[k][j]){
					d[i][j]=d[i][k]+d[k][j];
					pos[i][j]=k;
				}
			}
		}
	}
	if(ans==INF)cout<<"No solution.\n";
	else for(int i=0;i<cnt;i++)cout<<path[i]<<" \n"[i==cnt-1];
}

结合倍增

P2886 [USACO07NOV] Cow Relays G

题意

求经过k条边的最短路，允许重复走

思路

$定义d_{k,i,j} 为经过了k条边的i到j的最短路$
$转移方程：d_{a+b,i,j}=min(d_{a,i,k}+d_{b,k,j})$
暴力转移时间复杂度： $O(k^2n^3)$
考虑倍增与快速幂的思想，将k分离成 $2^0+2^1...$
只不过此时快速幂的两数相乘，变成两个数组跑floyd
时间复杂度: $O(n^3logk)$

cpp

int n,m,k,S,E;
int adj[N][N],tmp[N][N],res[N][N];
void mul(int c[][N],int a[][N],int b[][N]){
	memset(tmp,0x3f,sizeof tmp);
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++)tmp[i][j]=min(tmp[i][j],a[i][k]+b[k][j]);
		}
	}
	memcpy(c,tmp,sizeof tmp);
}
void qpow(){
	memset(res,0x3f,sizeof res);
	for(int i=1;i<=n;i++)res[i][i]=0;
	for(;k;k>>=1){
		if(k&1)mul(res,res,adj);
		mul(adj,adj,adj);
	}
}
void solve(){
	cin>>k>>m>>S>>E;
	memset(adj,0x3f,sizeof adj);
	map<int,int> ids;
	if(!ids.count(S))ids[S]=++n;
	if(!ids.count(E))ids[E]=++n;
	S=ids[S],E=ids[E];
	while(m--){
		int u,v,w;
		cin>>w>>u>>v;
		if(!ids.count(u))ids[u]=++n;
		if(!ids.count(v))ids[v]=++n;
		u=ids[u],v=ids[v];
		adj[u][v]=adj[v][u]=min(adj[u][v],w);
	}
	qpow();
	cout<<res[S][E]<<"\n";
}

删边最短路

CF1163F Indecisive Taxi Fee

题意：

每次改变无向图上的任意一条边，求最短路变化

思路：

预处理从1开始和从n开始的最短路 $disS,disT$
然后剖分出这条最短路径
如果当前修改边不在最短路径上，那么答案为 $\min(disS_n,disS_u+w+disT_v,disS_v+w+disT_u)$
如果在最短路径上，如果数值变小，那么最短路径显然变小；如果数值变大，那么最短路可能会改变
我们对最短路径上的边标号，记录在节点末端v从1到cnt，特殊地，节点1前面没有边标号为0
对于非最短路边，经过该边的最短路径一定会与原最短路有重合的部分，我们找出来，两条路径刚好相交的左端点和右端点，然后用线段树维护区间min即可

cpp

struct Node{
	int l,r,mn;
} t[N<<2];
int disS[N],disT[N],pre[N];
int head[N],e[M],ne[M],w[M],eid[M],idx,lp[N],rp[N];
int n,m,q;
bool onPath[N];
int path[M];
int path_cnt;
void addEdge(int a,int b,int c,int id){
	e[idx]=b,ne[idx]=head[a],w[idx]=c,eid[idx]=id,head[a]=idx++;
}
void dijk(int dis[],int st,int op){
	for(int i=1;i<=n;i++)dis[i]=INF;
	priority_queue<PII,vector<PII>,greater<>> pq;
	pq.push({0,st});
	dis[st]=0;
	while(!pq.empty()){
		auto [d,u]=pq.top();
		pq.pop();
		if(d>dis[u])continue;
		for(int i=head[u];~i;i=ne[i]){
			int v=e[i];
			if(dis[v]>d+w[i]){
				dis[v]=d+w[i];
				pre[v]=i;
				if(op==1&&!onPath[v])lp[v]=lp[u];
				if(op==2&&!onPath[v])rp[v]=rp[u];
				pq.push({dis[v],v});
			}
		}
	}
}
void trace(){
	int cur=1;
	lp[1]=rp[1]=0;
	onPath[1]=true;
	while(cur!=n){
		++path_cnt;
		int id=eid[pre[cur]];
		path[id]=path_cnt;
		cur=e[pre[cur]^1];
		onPath[cur]=true;
		lp[cur]=rp[cur]=path_cnt;
	}
}
void build(int p,int l,int r){
	t[p]={l,r,INF};
	if(l==r)return;
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}	
void modify(int p,int l,int r,int x){
	if(l>r)return;
	if(l<=t[p].l&&r>=t[p].r){
		t[p].mn=min(t[p].mn,x);
		return;
	}
	int mid=t[p].l+t[p].r>>1;
	if(l<=mid)modify(p<<1,l,r,x);
	if(r>mid)modify(p<<1|1,l,r,x);
}
int query(int p,int x){
	if(t[p].l==t[p].r)return t[p].mn;
	int res=t[p].mn;
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid)return min(res,query(p<<1,x));
	return min(res,query(p<<1|1,x));
}
void solve(){ 
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)head[i]=-1;
	vector<array<int,3>> edges;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		edges.push_back({u,v,w});
		addEdge(u,v,w,i);
		addEdge(v,u,w,i);
	}
	dijk(disT,n,0);
	trace();
	dijk(disS,1,1);
	dijk(disT,n,2);
	build(1,0,path_cnt);
	for(int i=0;i<m;i++){
		auto [u,v,w]=edges[i];
		if(path[i])continue;
		modify(1,lp[u]+1,rp[v],disS[u]+w+disT[v]);
		modify(1,lp[v]+1,rp[u],disS[v]+w+disT[u]);
	}
	while(q--){
		int t,x;
		cin>>t>>x;
		t--;
		auto [u,v,w]=edges[t];
		int ans;
		if(path[t]){
			ans=disS[n]-w+x;
			ans=min(ans,query(1,path[t]));
		}
		else{
			ans=disS[n];
			ans=min(ans,disS[u]+disT[v]+x);
			ans=min(ans,disS[v]+disT[u]+x);
		}
		cout<<ans<<"\n";
	}
}

最短路与DFS ​

P5764 [CQOI2005] 新年好 ​

题意 ​

思路 ​

最短路与二分 ​

P1948 [USACO08JAN] Telephone Lines S ​

题意 ​

思路 ​

最短路与拓扑排序 ​

P3008 [USACO11JAN] Roads and Planes G ​

题意 ​

思路 ​

最短路与dp ​

P1073 [NOIP2009 提高组] 最优贸易 ​

题意 ​

思路 ​

最短路计数问题 ​

法1：BFS ​

法2：Dijkstra ​

法3：SPFA ​

floyd的应用 ​

求最短路 ​

传递闭包 ​

模板 ​

P1347 排序 ​

题意 ​

思路 ​

最小环问题 ​

结合倍增 ​

P2886 [USACO07NOV] Cow Relays G ​

题意 ​

思路 ​

删边最短路 ​

CF1163F Indecisive Taxi Fee ​

P2685 [TJOI2012] 桥 ​

最短路与DFS

P5764 [CQOI2005] 新年好

题意

思路

最短路与二分

P1948 [USACO08JAN] Telephone Lines S

题意

思路

最短路与拓扑排序

P3008 [USACO11JAN] Roads and Planes G

题意

思路

最短路与dp

P1073 [NOIP2009 提高组] 最优贸易

题意

思路

最短路计数问题

法1：BFS

法2：Dijkstra

法3：SPFA

floyd的应用

求最短路

传递闭包

模板

P1347 排序

题意

思路

最小环问题

结合倍增

P2886 [USACO07NOV] Cow Relays G

题意

思路

删边最短路

CF1163F Indecisive Taxi Fee

P2685 [TJOI2012] 桥