负环&分层图

关于最短路算法的特殊应用

负环

洛谷 P3385【模板】负环

题意

给一个含有负权边的有向图，判断是否有负环存在

  • 负环：一个边权之和为负的环

算法

都说$SPFA$已死，其实拿来做这题还是很管用的

我们很容易想到：如果存在负环，那么环内所有点的最短路将会被无限次更新，$bfs$过程将会进入一个死循环，因此这里提供一个最好理解的思路：

  • 如果$SPFA$进行过程中同一个点被访问过超过$n$（$n$为节点个数）次，那么就一定存在负环（因为最坏情况下同一个点最多被访问$n$次）

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=2147483647;

struct Edge{
	int u,v,w,next;
}e[3005];

int n,m,cnt,vis[2005],head[200005],ring[2005]; 
//ring数组记录每个点访问了几次
inline void addedge(int u,int v,int w){
	e[++cnt].u=u;
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
int dis[2005];
inline bool SPFA(){ //裸spfa
	for(int i=1;i<=n;i++){
		dis[i]=inf;
	}
	queue<int> q;
	q.push(1);
	dis[1]=0;
	vis[1]=1;
	ring[1]=1; //起点初始为1次
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].v,w=e[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(vis[v]==0){
					ring[v]=ring[u]+1; //更新访问次数
					if(ring[v]>n) return true; //如果超过n了，则有负环
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return false;
}

int main(){
	int t;
	cin>>t;
	while(t--){
		cnt=0;
		memset(vis,0,sizeof(vis));
		memset(head,0,sizeof(head));
		memset(ring,0,sizeof(ring));
		memset(dis,0,sizeof(dis));
		cin>>n>>m;
		for(int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			addedge(u,v,w);
			if(w>=0) addedge(v,u,w);
		}
		if(SPFA()) cout<<"YE5"<<endl;
		else cout<<"N0"<<endl;
	}
	return 0;
}

2020.3.20 更新

桥豆麻袋，请看一下HDU 3666 THE MATRIX PROBLEM

这道题成功更新了我对于负环更新的理解（甚至让我加强了代码，玄学加强？）

于是查到有两种方案（玄学剪枝法）：

  1. 一个节点更新次数大于$\sqrt{n}$就判定位负环（无法证明？有什么办法，这题只能这么胡搞）

  2. 所有节点更新总次数大于$k*n$就判定为负环（一般k取2，然并卵，也是个玄学方法）

除此之外，我还发现我一直使用的判负环方法会WA？？

因此我得出结论：

对于此类题，先用我自己的判负环方法，如果WA了，改为更强的方法，如果还TLE，那么就用上面的玄学剪枝法

加强方法（SPFA内部）

1
2
3
4
5
6
7
while(!q.empty()){
		ll u=q.front();q.pop();
		vis[u]=0;
		ring[u]++; //新判法
	//if(ring[u]>sqrt(n)) return true; //超级玄学搞法
    //上面那个比较扯了，一般用下面这个就不会错了
    	if(ring[u]>n) return true;

分层图

蒟蒻在洛谷的第一道紫题orz
洛谷 P4568 飞行路线

题意

在单源最短路问题的基础上，加上以下条件：

  • 可以使得最多$k$条边的权值为$0$

算法一（动态规划）

由于$Dijkstra$算法的本质是动态规划，因此本题可以利用二维的动态规划求解

定义状态$dp[i][j]$：到达第$i$个节点使$j$条边权为零时的最短路

状态转移：两种状态

  1. 不使用免费机票：$dp[i][j]=dp[u][j]+w$，w为这条边的权值
  2. 使用免费机票：$dp[i][j]=dp[u][j-1]$，且$j>0$

注意：

  • 记得把对$k$的循环放在最外层
  • 此题是从0开始读入每条边的

代码（动态规划）

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
#include<bits/stdc++.h>
using namespace std;
const int inf=1<<30;
struct Edge{
	int u,v,w,next;
}e[500005];

struct node{
	int u,w;
	bool operator<(const node&rhs)const{
		return w>rhs.w;
	}
};

int n,m,k,s,t,cnt,head[1000005],dis[1000005][25];

inline void addedge(int u,int v,int w){
	e[++cnt].u=u;
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}

inline void dijkstra(){
	for(int i=0;i<n;i++){
		for(int j=0;j<=k;j++){
			dis[i][j]=inf;
		}
	}
	for(int i=0;i<=k;i++) dis[s][i]=0;
	
	priority_queue<node> q;
	for(int i=0;i<=k;i++){ //最外层
		q.push((node){s,0});
		while(!q.empty()){
			node q1=q.top();
			q.pop();
			int u=q1.u;
			if(q1.w>dis[u][i])continue;
			for(int p=head[u];p;p=e[p].next){
				int v=e[p].v,w=e[p].w;
				bool f=false;
				if(dis[v][i]>dis[u][i]+w){ //不使用免费机票
					dis[v][i]=dis[u][i]+w;
					f=true;
				}
				if(i>0&&dis[v][i]>dis[u][i-1]){ //使用免费机票
					dis[v][i]=dis[u][i-1];
					f=true;
				}
				if(f){
					q.push((node){v,dis[v][i]});
				}
			}
		}
	}
	
	
}

int main(){
	cin>>n>>m>>k>>s>>t;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		addedge(u,v,w);
		addedge(v,u,w);
	} 
	dijkstra();
	cout<<dis[t][k]<<endl;
	return 0; 
}
  • 2020.3.13 补

算法二（分层建图）

看这题之前，我们先看另一道容易一点的

HDU 4724 The Shortest Path in Nya Graph

题意：

求一个无向带权图的单源最短路

附加条件：每个节点都处在一个“层”中，可以花费c的代价在相邻两层的任意节点间移动

题解：

首先，毋庸置疑我们肯定得建图+求最短路，但这个附加条件就十分棘手了

因此，出现了分层建图这么一个概念：

我们将层与层之间的关系建立在原始的n个节点的图之后（虚图，也可以说是把每一层也视为一个节点），比方说，如果i号点在第k层，那么我们就建一个从点i指向第k层的单向边（边权为0），而这个第k层可以表示为n+k（就像食物链这道并査集一样，单独剥离一块区域用来存点和层的关系）因而这个就呈现出了点i在第k层的一个概念，而由于每相邻层之间的点能任意穿梭，我们还必须建立起相邻的层中点与层中点的关系，因此还需要存一次点i到前一层（如果i不在最后一层）和后一层（如果i不在第一层）的关系（依题意存双向边，边权为c），这样这个图就建好了，接下来跑一遍最短路就行了（当然这题似乎需要堆优化的dijkstra才能过）

代码（HDU 4724 分层图）

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1ll<<60;
inline ll read() {
	ll kk=0,f=1; 
	char cc=getchar(); 
	while(cc<'0'||cc>'9'){if(cc=='-')f=-1;cc=getchar();} 
	while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();} 
	return kk*f; 
}
int cnt,head[800005];
ll dis[800005];
int n,m,c;
struct Edge{
	int u,v,w,next;
}e[800005]; 
struct node{
	int u,dis;
	bool operator<(const node&rhs)const {
		return dis>rhs.dis;
	}
};

inline void addedge(int u,int v,int w){
	e[++cnt]=Edge{u,v,w,head[u]};
	head[u]=cnt;
}

inline void dij(){ //dijkstra最短路堆优化
	for(int i=1;i<=(n+n);i++) dis[i]=inf;
	dis[1]=0;
	priority_queue<node> q;
	q.push(node{1,0});
	while(!q.empty()){
		node q1=q.top();q.pop();
		ll u=q1.u,d=q1.dis;
		if(d>dis[u]) continue;
		for(int i=head[u];i;i=e[i].next){
			ll v=e[i].v,w=e[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(node{v,dis[v]});
			}
		}
	}
}

int main(){
	int t=read();
	for(int o=1;o<=t;o++){
		cnt=0;
		memset(head,0,sizeof(head));
		memset(e,0,sizeof(e)); 
		n=read(),m=read(),c=read();
		int x,y,z;
		for(int i=1;i<=n;i++){
			x=read();
			addedge(i,n+x,0); //记得是单向边，否则WA
			if(x>1){ //如果不在第一层，把连上前一层
				addedge(i,n+x-1,c);
				addedge(n+x-1,i,c);
			}
			if(x<n){ //如果不在最后一层，就连上下一层
				addedge(i,n+x+1,c);
				addedge(n+x+1,i,c);
			}
		}
		for(int i=1;i<=m;i++){ //正常加边操作
			x=read(),y=read(),z=read();
			addedge(x,y,z);
			addedge(y,x,z);
		}
		dij();
		printf("Case #%d: %lld\n",o,dis[n]==inf?-1:dis[n]);
	}
	return 0;
}

接下来我们再看这道 [飞行路线]

我们同样考虑分层建图，由于存在k次免费，因此我们建一个k+1层图，第一层是正常的不使用任何免费机票的图，从第二层往后，每加一层就视为使用了一次免费机票，因此最后只需要跑一遍从st到en+k*n的最短路即可

那么在建图的时候，我们在每一层都要正常建图，同时要把当前层往前一层的对应节点连一个边权为0的边，表示使用免费机票下的路线

代码（飞行路线 分层图）

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1ll<<60;
inline ll read() {
	ll kk=0,f=1; 
	char cc=getchar(); 
	while(cc<'0'||cc>'9'){if(cc=='-')f=-1;cc=getchar();} 
	while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();} 
	return kk*f; 
}
int cnt,head[8000005];
ll dis[8000005];
int n,m,k,st,en;
struct Edge{
	int u,v,w,next;
}e[8000005]; 
struct node{
	int u,dis;
	bool operator<(const node&rhs)const {
		return dis>rhs.dis;
	}
};

inline void addedge(int u,int v,int w=0){
	e[++cnt]=Edge{u,v,w,head[u]};
	head[u]=cnt;
}

inline void dij(int st){ //常规dijkstra堆优化
	memset(dis,0x3f3f,sizeof(dis));
	dis[st]=0;
	priority_queue<node> q;
	q.push(node{st,0});
	while(!q.empty()){
		node q1=q.top();q.pop();
		ll u=q1.u,d=q1.dis;
		if(d>dis[u]) continue;
		for(int i=head[u];i;i=e[i].next){
			ll v=e[i].v,w=e[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(node{v,dis[v]});
			}
		}
	}
}

int main(){
	n=read(),m=read(),k=read();
	st=read(),en=read();
	int u,v,w;
	for(int i=0;i<m;i++){
		u=read(),v=read(),w=read();
		addedge(u,v,w);
		addedge(v,u,w);
		for(int j=1;j<=k;j++){ //从第二层开始
			addedge(u+(j-1)*n,v+j*n); //连免费的边
			addedge(v+(j-1)*n,u+j*n);
			addedge(u+j*n,v+j*n,w); //连该层的正常边
			addedge(v+j*n,u+j*n,w);
		}
	}
	for(int i=1;i<=k;i++){
		addedge(en+(i-1)*n,en+i*n);
	}
	dij(st);
	printf("%lld\n",dis[en+k*n]);
	return 0;
}
算法
图论 数据结构 最短路

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！