最短路

发表于 | 分类于 | 阅读次数:

##Floyed
时间复杂度：$O(N^3)$

1
2
3
4
5
6
7
8
9
10

void floyed()
{
	int i,j,k;
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(dis[i][j]>dis[i][k]+dis[k][j])
					dis[i][j]=dis[i][k]+dis[k][j];
}

##Dijkstra
时间复杂度$O(Nlog_2N)$

复杂度低且稳定，但不能处理负边权图，最重要的是手写堆优化的Dijkstra洋洋洒洒上百行，易写错

其实Dijkstra与SPFA十分相似，只是Dijkstra通过贪心法减少了不必要的松弛操作

思路：

  • struct dat中存一个节点的目前最小路径长度和节点的标号
  • 以dat为元建立小根堆
  • 每次从小根堆取出一个不在S中的节点u，根据小根堆的性质，可以保证u是当前不在S中的点中最短路长度最小的点
  • 搜索与其相邻的不在S中的点进行松弛、入堆
  • 对每个节点进行过对u的此操作后，dis数组即为从v0出发到每个点的最短路

注意：
#include<queue>
bool operator<(const HN & ot)const{return v>ot.v;}

代码：

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
struct E{int to,next,value;} e[MAXM+1];int ecnt,G[MAXN+1];
void addEdge(int u,int v,int w){e[++ecnt]={v,G[u],w};G[u]=ecnt;}

struct HN
{
	int id,v;
	bool operator<(const HN & ot)const
	{
		return v>ot.v;
	}
};

priority_queue<HN> heap;

bool inS[MAXN*(MAXK+1)+1];
int dis[MAXN*(MAXK+1)+1];

void dijkstra(int v0)
{
	int i;
	for(i=1;i<=N*(K+1);i++) dis[i]=INF;
	memset(inS,false,sizeof(inS));
	dis[v0]=0;
	heap.push((HN){v0,0});
	while(!heap.empty())
	{
		int u=heap.top().id;heap.pop();
		if(inS[u]) continue;
		inS[u]=true;
		for(i=G[u];i;i=e[i].next)
		{
			int v=e[i].to;
			if(!inS[v])
				if(dis[v]>dis[u]+e[i].value)
				{
					dis[v]=dis[u]+e[i].value;
					heap.push((HN){v,dis[v]});
				}
		}
	}
}

##SPFA
时间复杂度：$O(NM)$
不太稳定，但能处理负边权图

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
struct E{int to,next,value;} e[MAXM+1];int ecnt,G[MAXN+1];
void addEdge(int u,int v,int w){e[++ecnt]={v,G[u],w};G[u]=ecnt;}

bool inQ[MAXN+1];
int dis[MAXN+1];

queue<int> que;
int SPFA(int v0)
{
	memset(vis,false,sizeof(vis));
	for(int i=1;i<=N;i++) dis[i]=INF;
	dis[v0]=0;		
	inQ[v0]=true;
	que.push(v0);
	while(!que.empty())
	{
		int u=que.front();que.pop();
		inQ[u]=false;
		for(int i=G[u];i;i=e[i].next)
		{
			int v=e[i].to;
			if(dis[v]>dis[u]+edge[i].value)
			{
				dis[v]=dis[u]+edge[i].value;
				if(!inQ[v])//如果以在队列里就不必再入队
				{
					inQ[v]=true;
					que.push(v);
				}
			}
		}
	}
}

##应用

说到最短路的应用，那简直是图论题目生产的支柱产业，甚至许多省选及以上难度的题目中也有最短路的影子。

参考：对偶图及其应用（最大流、最小割转化最短路）、图论中的二分（二分和最短路结合）、分层图（将会改变的图分层后跑最短路）

###[bzoj1003]物流运输[ZJOI2006]

题目描述

物流公司要把一批货物从码头 A 运到码头 B 。由于货物量比较大，需要 n 天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个 n 天的运输计划，使得总成本尽可能地小。

输入格式

第一行是四个整数 n （ $1\leq n\leq100$ ）、 m （ $1\leq m\leq20$ ）、 K 和 e 。 n 表示货物运输所需天数， m 表示码头总数， K 表示每次修改运输路线所需成本。接下来e行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编号以及航线长度（ $>0$ ）。其中码头 A 编号为 1 ，码头 B 编号为 m 。单位长度的运输费用为 1 。航线是双向的。再接下来一行是一个整数 d，后面的 d行 每行是三个整数 P （ $1 < P < m$ ）、 a 、 b （ $1\leq a\leq b \leq n$ ）。表示编号为 P 的码头从第 a 天到第 b 天无法装卸货物（含头尾）。同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一条从码头 A 到码头 B 的运输路线。

输出格式

包括了一个整数表示最小的总成本。总成本=n天运输路线长度之和+K*改变运输路线的次数。

本题的状态转移方程十分好想： $f[i]=min{f[j]+cost[j+1][i]+K},\ j\in[0,i)$

边界条件： $f[0]=-K$ （因为实际上 $j=0$ 时无需支付 $K$ ）

其中 $cost[i][j]$ 表示从第 $i$ 天到第 $j$ 天不变换航线需要的成本，这里需要用对每个 $i\in[1,n],j\in[i,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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

const int MAXN=105,MAXV=25,MAXE=MAXV*MAXV,INF=~0U>>5;

int n,m,K,en,d;
bool ban[MAXV][MAXN];//第i个码头在第j天是否被禁

struct E{int next,to,val;} e[MAXE<<1];int ecnt,G[MAXV];
void addEdge(int u,int v,int w)
{
	e[++ecnt]=(E){G[u],v,w};G[u]=ecnt;
	e[++ecnt]=(E){G[v],u,w};G[v]=ecnt;
}

int cost[MAXN][MAXN];
int dp[MAXN];

bool cantuse[MAXV];
int dis[MAXV];bool inS[MAXV];
struct HN
{
	int id,v;
	bool operator < (const HN & ot)const
	{return v>ot.v;}
};
priority_queue<HN> heap;
int dijkstra()
{
	int i;
	for(i=1;i<=m;i++) dis[i]=INF;
	memset(inS,false,sizeof(inS));
	dis[1]=0;heap.push((HN){1,0});
	while(!heap.empty())
	{
		int u=heap.top().id;heap.pop();
		if(inS[u]) continue;
		inS[u]=true;
		for(i=G[u];i;i=e[i].next)
		{
			int v=e[i].to;
			if(inS[v]||cantuse[v]) continue;
			if(dis[v]>dis[u]+e[i].val)
			{
				dis[v]=dis[u]+e[i].val;
				heap.push((HN){v,dis[v]});
			}
		}
	}
	return dis[m];
}
int main()
{
	int i,j,x,t;
	scanf("%d%d%d%d",&n,&m,&K,&en);
	for(i=1;i<=en;i++)
	{
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		addEdge(u,v,w);
	}
	scanf("%d",&d);
	for(i=1;i<=d;i++)
	{
		int P,l,r;scanf("%d%d%d",&P,&l,&r);
		for(j=l;j<=r;j++) ban[P][j]=true;
	}
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
		{
			memset(cantuse,false,sizeof(cantuse));
			for(x=2;x<m;x++)
				for(t=i;t<=j;t++)
					if(ban[x][t])
					{cantuse[x]=true;break;}
			cost[i][j]=dijkstra();
			if(cost[i][j]!=INF) cost[i][j]*=j-i+1;
		}
	for(i=1;i<=n;i++) dp[i]=INF;
	dp[0]=-K;
	for(i=1;i<=n;i++)
		for(j=0;j<i;j++)
			dp[i]=min(dp[i],dp[j]+cost[j+1][i]+K);
	printf("%d\n",dp[n]);
}

摧毁道路 destroy

给出一张 $n$ 个点 $m$ 条边的边权均为 $1$ 的无向图，求在保证 $dis(s_1,t_1)\leq l_1$ 且 $dis(s_2,t_2)\leq l_2$ 的前提下最多能删除的边数。

$n,m\leq3000$

我们希望在满足条件的情况下使用的边数最小，如果只有一对源汇点的话取最短路即可，但有两对的情况下不能简单相加，因为两个路径的公用边只需要计算一次。考虑枚举两个中转点 $u,v$ ，这两点之间的路径是公用的，则最少的边数即为 $dis(s_1,u)+dis(v,t_1)+dis(s_2,u)+dis(v,t_2)+dis(u,v)$ 和 $dis(s_1,u)+dis(v,t_1)+dis(s_2,v)+dis(u,t_2)+dis(u,v)$ 中的最小值，注意判断是否符合条件，时间复杂度 $O(n^2)$

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

const int MAXN=3e3+5,MAXM=6e3+5,INF=1e9;

int n,m,s1,t1,l1,s2,t2,l2;
struct E{int next,to;} e[MAXM];int ecnt,G[MAXN];
void addEdge(int u,int v){e[++ecnt]=(E){G[u],v};G[u]=ecnt;}
void addEdge2(int u,int v){addEdge(u,v);addEdge(v,u);}

int dis[MAXN][MAXN];
std::queue<int> que;
void calDis(int s)
{
	int i;
	for(i=1;i<=n;i++) dis[s][i]=INF;
	dis[s][s]=0;que.push(s);
	while(!que.empty())
	{
		int u=que.front();que.pop();
		for(i=G[u];i;i=e[i].next)
		{
			int v=e[i].to;
			if(dis[s][v]==INF)
			{
				dis[s][v]=dis[s][u]+1;
				que.push(v);
			}
		}
	}
}
inline void initDis(){for(int i=1;i<=n;i++) calDis(i);}

int main()
{
	freopen("destroy.in","r",stdin);
	freopen("destroy.out","w",stdout);
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		addEdge2(u,v);
	}
	initDis();
	scanf("%d%d%d%d%d%d",&s1,&t1,&l1,&s2,&t2,&l2);
	if(dis[s1][t1]>l1||dis[s2][t2]>l2) {printf("-1\n");return 0;}
	int ans=m-dis[s1][t1]-dis[s2][t2];
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if(dis[s1][i]+dis[i][j]+dis[j][t1]<=l1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=l2)
				ans=std::max(ans,m-dis[s1][i]-dis[s2][i]-dis[i][j]-dis[j][t1]-dis[j][t2]);
			if(dis[s1][i]+dis[i][j]+dis[j][t1]<=l1&&dis[s2][j]+dis[i][j]+dis[i][t2]<=l2)
				ans=std::max(ans,m-dis[s1][i]-dis[s2][j]-dis[i][j]-dis[j][t1]-dis[i][t2]);
		}
	printf("%d\n",ans);
	return 0;
}