poj 3463 Sightseeing 正权有向图最短路次短路的条数和长度模板

缘起

【1】和【2】中我们通过dijkstra、spfa两种方法给出了次短路模板. 现在我们研究次短路的条数问题. poj 3463 Sightseeing

分析

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
旅行团每天固定的从S地出发到达F地，为了省油要求尽量走最短路径或恰好比最短路径长1单位距离的路径
求满足条件的路径条数

【输入】
多样例.第一行是样例数. 然后每个样例开始于n和m,
2 ≤ N ≤ 1,000 and 1 ≤ M ≤ 10, 000
n是城市的个数, m是有向弧（即单向的）的条数. 然后是m行, 每行三个正整数A,B,L, 
1 ≤ A, B ≤ N, A ≠ B and 1 ≤ L ≤ 1,000,
表示从A到B的弧长L
最后一行是两个整数S和F, 1 ≤ S, F ≤ N and S != F, 即为题目中的起点和终点.

【输出】
对每个样例, 输出最短路或者恰好比它长1的次短路的条数之和. 输入保证答案最多1e9条。

【样例输入】
2
5 8
1 2 3
1 3 2
1 4 5
2 3 1
2 5 3
3 4 2
3 5 4
4 5 3
1 5
5 6
2 3 1
3 2 1
3 1 10
4 5 2
5 2 7
5 2 7
4 1

【样例输出】
3
2

【限制】
2s

其实和【1】、【2】一样,也都是在跑dijkstra或者spfa的时候顺便维护一些事情而已. 但是本文结合了【3】的优化（更快的板子）以及使用了比【1】、【2】更好理解的方式（之所以说是更加好的理解方式是因为它每次从堆中弹出的状态区分了到底是最短路还是次短路（通过flag），其实flag的作用根本不在于鉴别最短路还是次短路(代码里面根本没有用flag进行判断的),而是在于44行防止重复计数num.也就是说, 如果不是本题要计数num的话, 根本没必要使用flag）， 即下面的 if…else if…else if… 仅仅针对当前出堆的状态来更新. 以后做次短路就用这种方式, 学到了~

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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL
const int maxn = 1005, maxm = 10005;
int n,m, d[maxn][2], num[maxn][2], head[maxn],cnt,s,f; // d[i][0](d[i][1])是到达i顶点的最（次）短路, num[i][0]（num[i][1]）是到达i顶点的最（次）短路的条数
struct KK
{
	int v, c, flag; // v表示顶点, c表示路径长度, flag=0表示最短路,flag=1表示次短路
	KK(int v,int c,int flag):v(v),c(c),flag(flag){}
	bool operator <(const KK &o) const
	{
		return c>o.c; // c越大, 优先级越低
	}
};
bool v[maxn][2];
struct Arc
{
	int from,to,nxt,len;
}g[maxm];

void addarc(int from, int to, int len)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].len = len, g[cnt].nxt = head[from];
	head[from] = cnt++;
}

int solve()
{
	memset(d, 0x3f, sizeof(d));
	memset(num,0,sizeof(num));
	memset(v, 0, sizeof(v));
	d[s][0] = 0;
	num[s][0] = 1;
	priority_queue<KK > pq;
	pq.push(KK(s,0,0));
	while(!pq.empty())
	{
		KK top = pq.top();
		pq.pop();
		int h = top.v, flag = top.flag;
		if (v[h][flag]) // 如果状态达到过, 则不必再扩展了, 这就是【3】中最后提及的优化"更快的板子"
		{
			continue;
		}
		v[h][flag] = true;
		for (int i = head[h],to, t; ~i; i = g[i].nxt) // 下面的if...else if...else if 更加容易理解~
		{
			to  = g[i].to;
			t = d[h][flag]+g[i].len; // 松弛的长度
			if (!v[to][0] && d[to][0] > t) // 更新最短路、次短路
			{
				d[to][1] = d[to][0];
				num[to][1] = num[to][0]; // 更新次短路
				d[to][0] = t;
				num[to][0] = num[h][flag]; // 更新最短路
				pq.push(KK(to, d[to][1], 1));
				pq.push(KK(to, d[to][0], 0));
			}
			else if (!v[to][0] && d[to][0] == t) // 更新最短路方法数
			{
				num[to][0] += num[h][flag]; // 为什么可以直接相加, 是因为(h,flag) 是首次出现(上面的continue起的作用), 所以一定和原先的num[to][0]中的方案不重复,因为(h,flag)是新拓展(44行保证它从未出现过)出的状态. 
			}
			else if (!v[to][1] && d[to][1]>t) // 更新最短路
			{
				d[to][1] = t;
				num[to][1] = num[h][flag];
				pq.push(KK(to, d[to][1], 1));
			}
			else if (!v[to][1] && d[to][1] == t) // 更新次短路的方法数
			{
				num[to][1] += num[h][flag]; // 能直接相加的原因和上面更新最短路方法数的理由相同
			}
		}
	}
	if (d[f][0]+1==d[f][1]) // 如果次短路的确仅仅比最短路长1的话
	{
		num[f][0] += num[f][1];
	}
	return num[f][0];
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		cnt = 0;
		memset(head, -1, sizeof(head));
		scanf("%d%d", &n,&m);
		while(m--)
		{
			int a,b,l;
			scanf("%d%d%d", &a, &b, &l);
			addarc(a,b,l);
		}
		scanf("%d%d", &s, &f);
		printf("%d\n", solve());
	}
	return 0;
}

ac情况

Status Accepted
Time 32ms
Memory 408kB
Length 2357
Lang C++
Submitted 2019-10-28 16:44:55
Shared
RemoteRunId 20997897

其实, 在松弛的时候不加 !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
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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL
const int maxn = 1005, maxm = 10005;
int n,m, d[maxn][2], num[maxn][2], head[maxn],cnt,s,f; 
struct KK
{
	int v, c, flag; 
	KK(int v,int c,int flag):v(v),c(c),flag(flag){}
	bool operator <(const KK &o) const
	{
		return c>o.c; 
	}
};
bool v[maxn][2];
struct Arc
{
	int from,to,nxt,len;
}g[maxm];

void addarc(int from, int to, int len)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].len = len, g[cnt].nxt = head[from];
	head[from] = cnt++;
}

int solve()
{
	memset(d, 0x3f, sizeof(d));
	memset(num,0,sizeof(num));
	memset(v, 0, sizeof(v));
	d[s][0] = 0;
	num[s][0] = 1;
	priority_queue<KK > pq;
	pq.push(KK(s,0,0));
	while(!pq.empty())
	{
		KK top = pq.top();
		pq.pop();
		int h = top.v, flag = top.flag;
		if (v[h][flag]) 
		{
			continue;
		}
		v[h][flag] = true;
		for (int i = head[h],to, t; ~i; i = g[i].nxt) 
		{
			to  = g[i].to;
			t = d[h][flag]+g[i].len; 
			if (d[to][0] > t) // 在松弛的时候不加 !v[][] 这样的判断也是可以的
			{
				d[to][1] = d[to][0];
				num[to][1] = num[to][0]; 
				d[to][0] = t;
				num[to][0] = num[h][flag]; 
				pq.push(KK(to, d[to][1], 1));
				pq.push(KK(to, d[to][0], 0));
			}
			else if (d[to][0] == t) 
			{
				num[to][0] += num[h][flag]; 
			}
			else if (d[to][1]>t) 
			{
				d[to][1] = t;
				num[to][1] = num[h][flag];
				pq.push(KK(to, d[to][1], 1));
			}
			else if (d[to][1] == t) 
			{
				num[to][1] += num[h][flag]; 
			}
		}
	}
	if (d[f][0]+1==d[f][1]) 
	{
		num[f][0] += num[f][1];
	}
	return num[f][0];
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		cnt = 0;
		memset(head, -1, sizeof(head));
		scanf("%d%d", &n,&m);
		while(m--)
		{
			int a,b,l;
			scanf("%d%d%d", &a, &b, &l);
			addarc(a,b,l);
		}
		scanf("%d%d", &s, &f);
		printf("%d\n", solve());
	}
	return 0;
}

ac情况

Status Accepted
Time 32ms
Memory 412kB
Length 2305
Lang C++
Submitted 2019-10-29 07:28:21
Shared
RemoteRunId 21000037

综合上面两份代码, 我们考虑2个问题

  1. 为什么能保证一旦一个状态 v,flag 出堆之后, 该状态的num和d（即 num[v][flag] 和 d[v][flag] ） 就一定已经算好了.
  2. 为什么第二份ac代码中第53行可以去掉!v[to][0/1] 这样的判断也是可以的.

首先回答第一个问题. 其实类似的技巧已经在【3】中用过了. 反证法~

如果存在还没有出现的方案的话, 即存在某个点A, 使得A的某个状态(A,flag1)能（非严格）松弛当前出堆的状态 (v, flag). 则因为题目给定的图的权是严格正的. 所以(A,flag1)作为KK结构体的c属性一定严格<当前出堆的(v,flag)作为KK结构体的c属性. 但是按照我们使用小根堆, (A,flag1) 一定在(v,flag)前面出堆. 所以(A,flag1)已经出堆了（因为(v,flag)是当前出堆元素）, 而如果已经出堆的话, 则代码中的第44行是不会允许(A, flag1)去松弛(v,flag)的. 换言之, 能（非严格）松弛(v,flag)的状态一定已经全部出堆了. 所以一旦(v,flag)出堆了, 则它的num也好, d也好, 一定都算好了.

ps: 这里的非严格的意思就是允许>= 而不是严格的 >

再回答第二个问题. 其实和第一个问题是一个问题. 代码中的第49行的for循环中有4个if. 能进入到这4个if中都表示发生了（非严格）松弛. 而根据第一个问题的分析, 意味着被松弛的状态 (to,0/1) 一定是没有出堆的. 所以

v[to][0/1] 一定是false. 所以加不加!v[to][0/1] 这样的判断无所谓. 其实对于【3】文中的”其次”（【3】中全文检索一下”其次”就找到了）, 道理也是如此（即如果d[to]>g[x].len+d[h]的话, 则to一定没有出堆,否则h肯定先于to出堆, h就不可能是代码中当前出堆的元素了 ）——即【3】中代码的45行的

1
if (!v[to] && d[to]>g[x].len+d[h])

完全可以改成

1
if (d[to]>g[x].len+d[h])

从上面的分析就知道, 本题的正权条件对于上面的算法的真确性是本质的. 而【4】就缺失了这一条件. 这会导致【4】中的算法会发生根本性的变化. 感兴趣的读者可以参考【4】中的论述.

参考

【1】https://yfsyfs.github.io/2019/08/21/poj-3255-Roadblocks-dijkstra/

【2】https://yfsyfs.github.io/2019/10/28/POJ-3255-Roadblocks-%E6%AC%A1%E7%9F%AD%E8%B7%AF%E6%A8%A1%E6%9D%BF-spfa/

【3】https://yfsyfs.github.io/2019/08/22/hdu-2544-dijkstra%E6%A8%A1%E6%9D%BF/

【4】https://yfsyfs.github.io/2019/10/29/hdu-3191-How-Many-Paths-Are-There-%E5%90%AB0%E6%9D%83%E5%BC%A7%E7%9A%84%E9%9D%9E%E8%B4%9F%E6%9D%83%E6%9C%89%E5%90%91%E5%9B%BE%E6%AC%A1%E7%9F%AD%E8%B7%AF%E6%9D%A1%E6%95%B0%E5%92%8C%E9%95%BF%E5%BA%A6%E6%A8%A1%E6%9D%BF/