gyro永不抽风

ああああああああああああああああおおおおおおおおおおおおおおおお

发表于 分类于 Disqus：
本文字数： 1.4k 阅读时长 ≈ 1 分钟
博客园 同步已开启

题目

题目描述

今天是小Z的生日，同学们为他带来了一块蛋糕。这块蛋糕是一个长方体，被用不同色彩分成了N个相同的小块，每小块都有对应的幸运值。

小Z作为寿星，自然希望吃到的第一块蛋糕的幸运值总和最大，但小Z最多又只能吃M小块(M≤N)的蛋糕。

吃东西自然就不想思考了，于是小Z把这个任务扔给了学OI的你，请你帮他从这N小块中找出连续的k块蛋糕(k≤M)，使得其上的幸运值最大。

输入格式

输入文件cake.in的第一行是两个整数N,M。分别代表共有N小块蛋糕，小Z最多只能吃M小块。

第二行用空格隔开的N个整数，第i个整数Pi代表第i小块蛋糕的幸运值。

输出格式

输出文件cake.out只有一行，一个整数，为小Z能够得到的最大幸运值。

输入输出样例

输入 #1 
5 2
1 2 3 4 5
输出 #1 
9
输入 #2 
6 3
1 -2 3 -4 5 -6
输出 #2 
5

说明/提示

对20%的数据，N≤100。

对100%的数据，N≤500000，|Pi|≤500。 答案保证在2^31-1之内。

题解

设$f[i]$为以$i$个元素结尾的连续子段的最大值：

改写:

显而易见，我们要维护一个最小值的单调队列，也就是一个递增的单调队列，这样我们就可以得到线性的复杂度。

不过我的做法有点黑魔法（雾），我想的时候是这么想的：以第$i$个元素开始的连续子段的最大值，这样其实就要维护一个递减的单调队列，不过时间复杂度就变成了$O(m + n) \approx O(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
#include <iostream>
#include <cstdio>
#define int long long

using namespace std;

const int maxn = 500005 * 2;
struct node { int val, pos; } q[maxn];
int a[maxn], s[maxn], m, n;

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i]; s[i] = s[i - 1] + a[i]; 
	}
	for (int i = n + 1; i <= m + n; i ++) s[i] = s[n];
	int head = 0, tail = 0;
	int ans = -8e18;
	// max --> decrease
	for (int i = 1; i <= n + m; i ++) {
		while (head < tail && s[i] >= q[tail - 1].val) tail --;
		q[tail ++] = (node) { s[i], i };
		while (head < tail && i - q[head].pos + 1 > m) head ++;
		ans = max(ans, q[head].val - s[(i - m >= 0) ? i - m : 0]);
	}
	cout << ans << endl;
	return 0;
}

发表于 分类于 Disqus：
本文字数： 1.8k 阅读时长 ≈ 2 分钟
博客园 同步已开启

引言

再次写下这些东西，真的是感慨万千。从之前的只知道抄别人的，硬理解，到现在的查一下原理然后自己口胡，其中的辛酸大概也只有自己知道了。引用我很喜欢的一位数学老师的话：

只有体系建立起来了，才能办好事情。

单调队列的用途

一般来说，单调队列用在维护一个区间的极值上，即下面这两个式子：

正常情况下，时间复杂度应该为$O(mn)$。

单调队列的思想

单调队列，名为“单调”，意思就是队列当中元素是单调的。有一个很好的比方：你在排队买饭的时候，遇到比你弱的人，你就干掉然后插队，知道前面是比你强的人。这个时候你维护的就是一个单调递减的队列（因为你比你前面的人弱嘛），但是注意：你也在维护一个潜在的最大值的队列。

原因是这样的：当某个元素已经不在滑动窗口里面时，直接pop掉就行了，所以队首一定是区间最大值。

而区间最小值，只需要维护一个递增队列就行。

模板题目

题目描述

有一个长为 nn 的序列 aa，以及一个大小为 kk 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如：

The array is [1,3,−1,−3,5,3,6,7][1,3,-1,-3,5,3,6,7], and k=3k = 3。

输入格式

输入一共有两行，第一行有两个正整数 n,kn,k。 第二行 nn 个整数，表示序列 aa

输出格式

输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值

输入输出样例

输入 #1 
8 3
1 3 -1 -3 5 3 6 7
输出 #1 
-1 -3 -3 -3 3 3
3 3 5 5 6 7

说明/提示

【数据范围】
对于 50%50\% 的数据，1≤n≤1051 \le n \le 10^5；
对于 100%100\% 的数据，1≤k≤n≤1061\le k \le n \le 10^6，ai∈[−231,231)a_i \in [-2^{31},2^{31})。

代码

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
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long

using namespace std;

const int maxn = 1000006; 
int n, k, a[maxn];

struct node { int val, pos; } q[maxn];

signed main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	int head = 0, tail = 0;
	// find min -> increase
	for (int i = 1; i <= n; i ++) {
		while (head < tail && a[i] <= q[tail - 1].val) tail --;
		q[tail ++] = (node) { a[i], i };
		while (head < tail && i - q[head].pos + 1 > k) head ++;
		if (i >= k) cout << q[head].val << (i == n ? "\n" : " ");
	}
	// find max -> decrease
	head = 0, tail = 0;
	for (int i = 1; i <= n; i ++) {
		while (head < tail && a[i] >= q[tail - 1].val) tail --;
		q[tail ++] = (node) { a[i], i };
		while (head < tail && i - q[head].pos + 1 > k) head ++;
		if (i >= k) cout << q[head].val << (i == n ? "\n" : " ");
	}
	return 0;
}

发表于 分类于 Disqus：
本文字数： 2.4k 阅读时长 ≈ 2 分钟
博客园 同步已开启

题目

题目背景

英文题面见此链接

题目描述

John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。

John 的每个农场有 mm 条小路（无向边）连接着 nn 块地（从 1∼n1 \sim n 标号），并有 ww 个虫洞。

现在 John 想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。

输入格式

输入的第一行是一个整数 TT，代表测试数据的组数。

每组测试数据的格式如下：

每组数据的第一行是三个用空格隔开的整数，分别代表农田的个数 nn，小路的条数 mm，以及虫洞的个数 ww。

每组数据的第 22 到第 (m+1)(m + 1) 行，每行有三个用空格隔开的整数 u,v,pu, v, p，代表有一条连接 uu 与 vv 的小路，经过这条路需要花费 pp 的时间。

每组数据的第 (m+2)(m + 2) 到第 (m+w+1)(m + w + 1) 行，每行三个用空格隔开的整数 u,v,pu, v, p，代表点 uu 存在一个虫洞，经过这个虫洞会到达点 vv，并回到 pp 秒之前。

输出格式

对于每组测试数据，输出一行一个字符串，如果能回到出发时刻之前，则输出 YES，否则输出 NO。

输入输出样例

输入 #1 
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
输出 #1 
NO
YES

说明/提示

样例 2 解释

John 只需要沿着 1→2→3→11 \rightarrow 2 \rightarrow 3 \rightarrow 1 的路径一直转圈即可，每转完一圈，时间就会减少一秒。

数据范围与约定

对于 100%100\% 的数据，1≤T≤51 \le T \le 5，1≤n≤5001 \le n \le 500，1≤m≤25001 \le m \le 2500，1≤w≤2001 \le w \le 200，1≤p≤1041 \le p \le 10^4。

题解

这里其实很显然，就是要求有没有负环。这里我主要想说的是为什么在这道题当中，从任意一点出发跑SPFA都是可以判断的。首先，在没有虫洞的情况下，图是双向且连同的，那就意味着无论如何我们都可以在节点之间往返。所以，如果在某一点存在一个负环，那必定可以从其他任意一点到达，从而不断优化最短路，达到用SPFA判断负环的目的。

代码

下面是代码，其实就是裸的SPFA

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
#include <iostream>
#include <queue>
#include <cstring>
#define int long long

using namespace std;

const int maxm = 25005;
const int maxn = 5005;
const int maxw = 2005;

int n, m, T, w, ecnt = 2, head[maxn], dis[maxn], cnt[maxn];
bool in[maxn];
struct edge { int to, next, w; } g[(maxm << 1) + maxw];
void add_edge(int u, int v, int w) { g[ecnt] = (edge) { v, head[u], w }; head[u] = ecnt ++; }
struct node { int dis, pos; };

bool spfa() {
	for (int i = 1; i <= n; i ++) dis[i] = 2e9, in[i] = false;
	queue<node> q;
	dis[1] = 0; q.push((node) { dis[1], 1 });
	in[1] = true;
	cnt[1] = 0;
	while (!q.empty()) {
		int u = q.front().pos; q.pop(); in[u] = false;
		for (int e = head[u]; e; e = g[e].next) {
			int v = g[e].to;
			if (dis[v] > dis[u] + g[e].w) {
				dis[v] = dis[u] + g[e].w;
				cnt[v] = cnt[u] + 1;
				if (cnt[v] >= n) return true;
				if (!in[v]) {
					q.push((node) { dis[v], v });
					in[v] = true;
				}
			}
		}
	}
	return false;
}

signed main() {
	cin >> T;
	while (T --> 0) {
		cin >> n >> m >> w;
		ecnt = 2;
		memset(head, 0, sizeof(head));
		memset(g, 0, sizeof(g));
		for (int i = 1; i <= m; i ++) {
			int u, v, p; cin >> u >> v >> p;
			add_edge(u, v, p);
			add_edge(v, u, p); 
		}
		for (int i = 1; i <= w; i ++) {
			int u, v, p; cin >> u >> v >> p;
			add_edge(u, v, -p);
		}
		bool ans = spfa();
		cout << (ans ? "YES" : "NO") << endl;
	}
	return 0;
}

发表于 分类于 Disqus：
本文字数： 543 阅读时长 ≈ 1 分钟

完结撒花，感谢陪伴。

从初三上的十月七号的24:30到现在，整整两年的Alicization篇终于完结了。

我至今记得那个国庆假期的最后一天的凌晨，我躺在床上等着SAO开播，之前十点半的一档是终将成为你。

Alicization见证了我初三上每周六的快乐，见证了我下午买回家的晚上用保温杯里的热水偷偷泡的泡面，见证了我高一上的无忧无虑，也见证了我的当下，和这过去这个让我保守拷打的暑假。她确实见证了我过去的两年，从懵懂和无知，从毫无主见随风而倒，到些许的成熟？（雾

虽然故事的叙述和对原作的改编让人接受不能，整部作品饱受争议，评分一度走低，但仍不能将作品贬得一无是处。

纵使经费充足，因为意外，赶工却仍在发生，但无论是作画质量还是画面数量都保持在可以接受的范围之内，甚至说，超乎原有的预估。

创新性的摄影处理让人大开眼界，让原本就已不错的原画提升了一个层次，极富美感和高级感，属实惊艳。特别是后半段打戏有增无减，在如此密集的工作量下还能保持这样的水准确实让人肃然起敬。这一组动画人，真的让人钦佩。值得尊重。

以及，最后一集留下了这么多坑，如果真的没有续作的话，我是不信的（否则着胆子也太大了

此外，进击篇的企划出了，让我们在艾恩葛朗特再会。换了监督，希望桐人和亚丝娜的狗粮能让我吃到饱。

SAO，yyds

发表于 分类于 Disqus：
本文字数： 2.8k 阅读时长 ≈ 3 分钟
博客园 同步已开启

关于SPFA

他死了。

SPFA原理

还是根据图论基本方程进行松弛操作，当无法继续松弛的时候，其实就已经达到了最优化，求出了单源最短路了。

为什么SPFA死了

因为数据很好卡。因为SPFA用的是双端队列，所以对于一些精心构造的图来说，复杂度其实是可以退化到$O(mn)$的。

为什么SPFA死了还要用

  • 因为可以求负环
  • 因为可以求带有负权边的最短路

SPFA和Dijkstra的区别

  • Dijkstra+heap是用小根堆，每次取出$\text {dis}$最小的点，来更新距离，那么这个点来说，最小距离就是当前的d。
  • SPFA是用双端队列，每次取出队头，来更新距离，它之后可能还会入队。它是一种动态逼近法，因为每次松弛距离都会减小，所以松弛一定会有结束的。如果一个点入队超过$n$次就是存在负环。
  • 如果是稠密图，Dijkstra + Heap比SPFA快。稀疏图则SPFA更快。SPFA可以有SLF和LLL两种优化，SLF就是$\text {dis}$比队头小就插入队头，否则插入队尾。
  • Dijkstra和Prim也很相似，它们的区别主要是d的含义，前者是到s的临时最短距离，后者是到树的临时最短距离，相同点是，每次找d最小的更新其它点的距离。

Ref: https://www.cnblogs.com/flipped/p/6830073.html

如何用SPFA判断负环

我们现在来思考一个问题：如果一张图上有$n$个点，那如果一条路径上有超过$n$个点会怎么样？

根据容斥原理，我们必定可以在路径上找到两个相同的点。换句话说，从一个点出发，又回到了这个点。然而整个过程确实求最短路的过程，路程$\text {dis}$不断在优化，所以这个环一定是负环（即路径和为负数）。而一条路径上有超过$n$个点，等价于一条路径有不少于$n$条边。而判断路径有多少条边其实非常容易，我们只需要在做松弛操作的时候更新记录路径条数的$\text {cnt}$数组就可以了：

题目

题目描述

给定一个 nn 个点的有向图，请求出图中是否存在从顶点 11 出发能到达的负环。

负环的定义是：一条边权之和为负数的回路。

输入格式

本题单测试点有多组测试数据。

输入的第一行是一个整数 TT，表示测试数据的组数。对于每组数据的格式如下：

第一行有两个整数，分别表示图的点数 nn 和接下来给出边信息的条数 mm。

接下来 mm 行，每行三个整数 u,v,wu, v, w。

  • 若 w≥0w \geq 0，则表示存在一条从 uu 至 vv 边权为 ww 的边，还存在一条从 vv 至 uu 边权为 ww 的边。
  • 若 w<0w < 0，则只表示存在一条从 uu 至 vv 边权为 ww 的边。

输出格式

对于每组数据，输出一行一个字符串，若所求负环存在，则输出 YES，否则输出 NO。

输入输出样例

输入 #1 
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8
输出 #1 
NO
YES

说明/提示

数据规模与约定

对于全部的测试点，保证：

  • 1≤n≤2×1031 \leq n \leq 2 \times 10^3，1≤m≤3×1031 \leq m \leq 3 \times 10^3。
  • 1≤u,v≤n1 \leq u, v \leq n，−104≤w≤104-10^4 \leq w \leq 10^4。
  • 1≤T≤101 \leq T \leq 10。

提示

请注意，mm 不是图的边数。

代码

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

using namespace std;

const int maxm = 3005;
const int maxn = 2005;
int ecnt = 2;
int n, m;
int head[maxn], dis[maxn], cnt[maxn];
bool in[maxn];
struct edge { int to, next, w; } g[maxm << 1];
void add_edge(int u, int v, int w) { g[ecnt] = (edge) { v, head[u], w }; head[u] = ecnt ++; }
struct node { int dis, pos; };


bool spfa() {
	for (int i = 1; i <= n; i ++)
		dis[i] = 2e9, in[i] = false;
	queue<node> q;
	dis[1] = 0; q.push((node) { dis[1], 1 });
	cnt[1] = 0; in[1] = true;
	while (!q.empty()) {
		int u = q.front().pos; q.pop();
		in[u] = false;
		for (int e = head[u]; e; e = g[e].next) {
			int v = g[e].to;
			if (dis[v] > dis[u] + g[e].w) {
				dis[v] = dis[u] + g[e].w;
				cnt[v] = cnt[u] + 1;
				if (cnt[v] >= n) return true;
				if (!in[v]) {
					q.push((node) { dis[v], v });
					in[v] = true;
				}
			}
		}
	}
	return false;
}

int main() {
	int T; cin >> T;
	while (T --> 0) {
		ecnt = 2;
		memset(g, 0, sizeof(g));
		memset(head, 0, sizeof(head));
		cin >> n >> m;
		for (int i = 1; i <= m; i ++) {
			int u, v, w; cin >> u >> v >> w;
			if (w >= 0) {
				add_edge(u, v, w);
				add_edge(v, u, w);
			} else add_edge(u, v, w);
		}
		cout << (spfa() ? "YES" : "NO") << endl;
	}
	return 0;
}

发表于 分类于 Disqus：
本文字数： 4.7k 阅读时长 ≈ 4 分钟
博客园 同步已开启

题目

题目描述

19441944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形，其南北方向被划分为 NN 行，东西方向被划分为 MM 列，于是整个迷宫被划分为 N×MN\times M 个单元。每一个单元的位置可用一个有序数对(单元的行号，单元的列号)来表示。南北或东西方向相邻的 22 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分成PP 类，打开同一类的门的钥匙相同，不同类门的钥匙不同。

大兵瑞恩被关押在迷宫的东南角，即 (N,M)(N,M) 单元里，并已经昏迷。迷宫只有一个入口，在西北角。也就是说，麦克可以直接进入 (1,1)(1,1) 单元。另外，麦克从一个单元移动到另一个相邻单元的时间为 11，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。

试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。

输入格式

第 11 行有 33 个整数，分别表示 N,M,PN,M,P 的值。

第 22 行是 11 个整数 KK，表示迷宫中门和墙的总数。

第 I+2I+2 行(1≤I≤K)(1\leq I\leq K)，有 55 个整数，依次为Xi1,Yi1,Xi2,Yi2,GiX_{i1},Y_{i1},X_{i2},Y_{i2},G_i：

  • 当 Gi≥1G_i \geq 1 时，表示 (Xi1,Yi1)(X_{i1},Y_{i1}) 单元与 (Xi2,Yi2)(X_{i2},Y_{i2}) 单元之间有一扇第 GiG_i 类的门

  • 当 Gi=0G_i=0 时，表示 (Xi1,Yi1)(X_{i1},Y_{i1}) 单元与 (Xi2,Yi2)(X_{i2},Y_{i2}) 单元之间有一堵不可逾越的墙（其中，∣Xi1−Xi2∣+∣Yi1−Yi2∣=1|X_{i1}-X_{i2}|+|Y_{i1}-Y_{i2}|=1，0≤Gi≤P0\leq G_i\leq P）。

第 K+3K+3 行是一个整数 SS，表示迷宫中存放的钥匙总数。

第 K+3+JK+3+J 行(1≤J≤S)(1\leq J\leq S)，有 33 个整数，依次为 Xi1,Yi1,QiX_{i1},Y_{i1},Q_i：表示第 JJ 把钥匙存放在 (Xi1,Yi1)(X_{i1},Y_{i1})单元里，并且第 JJ 把钥匙是用来开启第 QiQ_i 类门的。（其中1≤Qi≤P1\leq Q_i\leq P）。

输入数据中同一行各相邻整数之间用一个空格分隔。

输出格式

将麦克营救到大兵瑞恩的最短时间的值输出。如果问题无解，则输出 −1-1。

输入输出样例

输入 #1 
4 4 9
9
1 2 1 3 2
1 2 2 2 0
2 1 2 2 0
2 1 3 1 0
2 3 3 3 0
2 4 3 4 1
3 2 3 3 0
3 3 4 3 0
4 3 4 4 0
2
2 1 2
4 2 1
输出 #1 
14

说明/提示

∣Xi1−Xi2∣+∣Yi1−Yi2∣=1,0≤Gi≤P|X_{i1}-X_{i2}|+|Y_{i1}-Y_{i2}|=1,0\leq G_i\leq P

1≤Qi≤P1\leq Q_i\leq P

N,M,P≤10,K<150,S≤14N,M,P\leq10, K<150,S\leq 14

题解

题目中问要花费的最短时间，那其实就可以联想到最短路问题或者直接BFS。那记下来的问题就在于如何建图。我们可以发现，这里有着$p$把钥匙，要处理好这些钥匙是问题的关键。所以，我们可以建立分层图，而且分层图的层数是当前所有的钥匙的状态压缩。

形象地解释的话：如果现在是$i$层，那么我们先将$i$转换为二进制（假设一共有4种钥匙种类，那么$i$可能是：

意思就是有着第一种、第三种、第四种钥匙的层（从后往前看）。如果无法理解分层图，那么不妨看看前两篇博文，都是分层图的题。

所以接下来，我们只需要关心如何建立图，图建立好之后我们就可以扔给堆优化过的Dijkstra直接算就行了。

我们根据以下几点建图：

  • 如果有不可逾越的墙，不连边
  • 如果输入中没有提到这条边，在每层都连
  • 如果输入中提到了，且需要钥匙，那么先循环，然后按位运算匹配当前层是否拥有开门钥匙。若有则连边
  • 如果这一点有钥匙，那么在这个点，从所有没有钥匙的层，可以转移到有钥匙的层，连边。

最后答案其实就是把每一层的$(N, M)$遍历一遍去一个最小。

代码

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

using namespace std;

const int maxg = 10;
const int maxk = 155;
const int maxs = 15;
const int maxn = 11;
const int maxm = 11;
int n, m, p, k, s;
int ecnt = 2;
int head[maxn * maxm * (1 << maxg)], dis[maxn * maxm * (1 << maxg)];
bool vis[maxn * maxm * (1 << maxg)];
struct edge { int to, next, w; } g[(1 << maxg) * (maxk * 2 * 4 + maxs)];
void add_edge(int u, int v, int w) { g[ecnt] = (edge) { v, head[u], w }; head[u] = ecnt ++; } 
void add_edge(int x1, int y1, int l1, int x2, int y2, int l2, int w) {
	add_edge(y1 + (x1 - 1) * m + m * n * l1, 
			 y2 + (x2 - 1) * m + m * n * l2, w);
}
inline int id (int x, int y) {
    return (x - 1) * m + y ;
}
int map[200][200];

struct node {
	int dis, pos;
	friend bool operator < (const node &a, const node &b) { return a.dis > b.dis; }
};
priority_queue<node> q;

void dijkstra() {
	for (int i = 1; i <= m * n * (1 << p); i ++) dis[i] = 2e9;
	dis[1] = 0;
	q.push((node) { dis[1], 1 });
	while (!q.empty()) {
		int u = q.top().pos; q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int e = head[u]; e; e = g[e].next) {
			int v = g[e].to;
			if (dis[v] > dis[u] + g[e].w) {
				dis[v] = dis[u] + g[e].w;
				q.push((node) { dis[v], v });
			}
		}
	}
}

int main() {
	cin >> n >> m >> p >> k;
	for (int i = 1; i <= k; i ++) {
		int x1, x2, y1, y2, g;
		cin >> x1 >> y1 >> x2 >> y2 >> g;
		if (g == 0) g = -1;
		map[id(x1, y1)][id(x2, y2)] = g;
		map[id(x2, y2)][id(x1, y1)] = g;
	}
	for (int l = 0; l < (1 << p); l ++) {
		for (int i = 1; i <= n; i ++) { // x
			for (int j = 1; j <= m; j ++) { // y
				// right
				if (j < m) {
					int g = map[id(i, j)][id(i, j + 1)];
					if (g == 0) {
						add_edge(i, j, l, i, j + 1, l, 1);
						add_edge(i, j + 1, l, i, j, l, 1);
					}
					if ((l & (1 << (g - 1))) && (g != 0) && (g != -1)) {
						add_edge(i, j, l, i, j + 1, l, 1);
						add_edge(i, j + 1, l, i, j, l, 1);
					}
				}
				// down
				if (i < n) {
					int g = map[id(i, j)][id(i + 1, j)];
					if (g == 0) {
						add_edge(i, j, l, i + 1, j, l, 1);
						add_edge(i + 1, j, l, i, j, l, 1);
					}
					if ((l & (1 << (g - 1))) && (g != 0) && (g != -1)) {
						add_edge(i, j, l, i + 1, j, l, 1);
						add_edge(i + 1, j, l, i, j, l, 1);
					}
				}
			} 
		}
	}
	cin >> s;
	for (int i = 1; i <= s; i ++) {
		int x, y, q; cin >> x >> y >> q;
		for (int l = 0; l < (1 << p); l ++) {
			if (l & (1 << (q - 1))) continue;
			add_edge(x, y, l, x, y, (l | (1 << (q - 1))), 0);
		}
	}
	dijkstra();
	int ans = 2e9;
	for (int i = 1; i <= (1 << p); i ++) ans = min(ans, dis[m * n * i]);
	if (ans == 2e9) ans = -1;
	cout << ans << endl;
	return 0;
}

感谢

感谢@nwt（在右边的友链里 wennitao），在debug的时候提供了莫大的帮助。（qhy是屑）

发表于 更新于 分类于 Disqus：
本文字数： 3.3k 阅读时长 ≈ 3 分钟
博客园 同步已开启

题目

题目描述

给定一个 N×NN \times N 的方形网格，设其左上角为起点◎，坐标(1,1)(1,1)，XX 轴向右为正， YY 轴向下为正，每个方格边长为 11 ，如图所示。

一辆汽车从起点◎出发驶向右下角终点▲，其坐标为 (N,N)(N,N)。

在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则:

  1. 汽车只能沿网格边行驶，装满油后能行驶 KK 条网格边。出发时汽车已装满油，在起点与终点处不设油库。

  2. 汽车经过一条网格边时，若其 XX 坐标或 YY 坐标减小，则应付费用 BB ，否则免付费用。

  3. 汽车在行驶过程中遇油库则应加满油并付加油费用 AA。

  4. 在需要时可在网格点处增设油库，并付增设油库费用 CC(不含加油费用AA )。

  5. N,K,A,B,CN,K,A,B,C 均为正整数， 且满足约束: 2≤N≤100,2≤K≤102\leq N\leq 100,2 \leq K \leq 10。

设计一个算法，求出汽车从起点出发到达终点所付的最小费用。

输入格式

文件的第一行是 N,K,A,B,CN,K,A,B,C 的值。

第二行起是一个N×NN\times N 的 0−10-1 方阵,每行 NN 个值,至 N+1N+1 行结束。

方阵的第 ii 行第 jj 列处的值为 11 表示在网格交叉点 (i,j)(i,j) 处设置了一个油库,为 00 时表示未设油库。各行相邻两个数以空格分隔。

输出格式

程序运行结束时,输出最小费用。

输入输出样例

输入 #1 
9 3 2 3 6
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 1 0 0
1 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0 0
输出 #1 
12

说明/提示

2≤n≤100,2≤k≤102 \leq n \leq 100,2 \leq k \leq 10

题解

这道题一开始分层图的建立着实没有想出来，甚至看了题解都没想出来（我，菜）。所以特此记录。其实是这样的，因为一辆车总共只有$k$格油，所以我们可以建立$k + 1$层图，第$i$层图代表已经用掉了多少油。

接下来，我们考虑这个图如何构建：

  • 我们用三元组$(i, j, l)$来表示点，意为：第$l$层中的$(i, j)$
  • 因为题目中说不消耗钱的话只能向右或者向下，所以：
  • 因为题目中说向左或者向上要花钱，所以：
  • 在加油站的时候，情况和上面的就不太一样了，加油站的点应该都要指向该点的第$0$层（因为油必须加满），而且费用为$A$:
  • 还有就是不在加油站时可以随意添加油站，就是要花钱罢了：

在图建立完之后，我们就可以发现：求最小费用其实就是求最短路，然后最后无论剩多少油都是可能的，所以我们要把$(n, n, l)$都遍历一下取一个最小。

还有一点：要注意不要数组越界，这就是为什么代码里有好多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
#include <iostream>
#include <queue>
#include <cstdio>

using namespace std;

const int MAXN = 105;
const int MAXK = 15;

int n, k, a, b, c;
int head[MAXN * MAXN * MAXK], dis[MAXN * MAXN * MAXK], ecnt = 2;
bool vis[MAXN * MAXN * MAXK];
struct edge { int to, next, w; } g[2 * 7 * MAXK * MAXN * MAXN];
void add_edge(int u, int v, int w) { g[ecnt] = (edge) { v, head[u], w }; head[u] = ecnt ++; }
void add_edge(int x1, int y1, int l1, int x2, int y2, int l2, int w) {
	add_edge((y1 - 1) * n + x1 + l1 * n * n, (y2 - 1) * n + x2 + l2 * n * n, w);
}

struct node {
	int dis, pos;
	friend bool operator < (const node &a, const node &b) { return a.dis > b.dis; }
};
priority_queue<node> q;

void dijkstra() {
	for (int i = 1; i <= n * n * (k + 1); i ++) dis[i] = ((1 << 30) - 1) * 2;
	dis[1] = 0;
	q.push((node) { dis[1], 1 });
	while (!q.empty()) {
		int u = q.top().pos; q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int e = head[u]; e; e = g[e].next) {
			int v = g[e].to;
			if (dis[v] > dis[u] + g[e].w) {
				dis[v] = dis[u] + g[e].w;
				q.push((node) { dis[v], v });
			}
		}
	}
}

int main() {
	cin >> n >> k >> a >> b >> c;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j ++) {
			int oil = 0; cin >> oil;
			if (oil) {
				for (int l = 1; l <= k; l ++)
					add_edge(j, i, l, j, i, 0, a);
				if (i < n) add_edge(j, i, 0, j, i + 1, 1, 0);
				if (j < n) add_edge(j, i, 0, j + 1, i, 1, 0);
				if (i > 1) add_edge(j, i, 0, j, i - 1, 1, b);
				if (j > 1) add_edge(j, i, 0, j - 1, i, 1, b);
			} else {
				for (int l = 0; l < k; l ++) {
					if (i < n) add_edge(j, i, l, j, i + 1, l + 1, 0);
					if (j < n) add_edge(j, i, l, j + 1, i, l + 1, 0);
					if (i > 1) add_edge(j, i, l, j, i - 1, l + 1, b);
					if (j > 1) add_edge(j, i, l, j - 1, i, l + 1, b);
				}
				for (int l = 1; l <= k; l ++)
					add_edge(j, i, l, j, i, 0, c + a);
			}
		}
	}
	dijkstra();
	int ans = ((1 << 30) - 1) * 2;
	for (int l = 0; l <= k; l ++) ans = min(ans, dis[n * n * (1 + l)]);
	cout << ans << endl;
	return 0;
}

发表于 更新于 分类于 Disqus：
本文字数： 2.5k 阅读时长 ≈ 2 分钟
博客园 同步已开启

题目

题目描述

Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在nn个城市设有业务，设这些城市分别标记为 00 到 n−1n-1，一共有 mm 种航线，每种航线连接两个城市，并且航线有一定的价格。

Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 kk 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少？

输入格式

第一行三个整数 n,m,kn,m,k，分别表示城市数，航线数和免费乘坐次数。

接下来一行两个整数 s,ts,t，分别表示他们出行的起点城市编号和终点城市编号。

接下来 mm 行，每行三个整数a,b,ca,b,c，表示存在一种航线，能从城市 aa 到达城市 bb，或从城市 bb 到达城市 aa，价格为 cc。

输出格式

输出一行一个整数，为最少花费。

输入输出样例

输入 #1 
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100
输出 #1 
8

说明/提示

数据规模与约定

对于 30%30\% 的数据，2≤n≤50,1≤m≤300,k=02 \le n \le 50,1 \le m \le 300,k=0。

对于 50%50\% 的数据，2≤n≤600,1≤m≤6×103,0≤k≤12 \le n \le 600,1 \le m \le 6\times10^3,0 \le k \le 1。

对于 100%100\% 的数据，2≤n≤104,1≤m≤5×104,0≤k≤10,0≤s,t,a,b≤n,a≠b,0≤c≤1032 \le n \le 10^4,1 \le m \le 5\times 10^4,0 \le k \le 10,0\le s,t,a,b\le n,a\ne b,0\le c\le 10^3。

另外存在一组 hack 数据。

题解

由于可以有$k$次免费，这里构建分层图：

  • 有$k+1$层完全一样的图
  • 每条边在层与层之间单向连接，但是费用为0

那么这样构建的图的第$i$层的$t$点就是免费了$i - 1$次的最小费用。

方程：

常见问题

  • 如何防止从下面的层去上面？单向
  • 如何建图？思考一下OpenCV当中的图像，其实他们的内存地址是连续的，所以我们可以把他们放在一个一维数组当中，只不过开了$n\times k$个点罢了。

图片（Ref @SuperJvRuo）

代码

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
#include <iostream>
#include <stdio.h>
#include <queue>
#define int long long

using namespace std;

int ecnt = 2;
int n, m, k, s, t;
int head[150005], dis[150005], vis[150005];
struct edge { int to, next, w; } g[3000001];
void add_edge(int u, int v, int w) { g[ecnt] = (edge) { v, head[u], w }; head[u] = ecnt ++; }
void add_edge(int u, int v, int w, int l) { add_edge(u + l * n, v + l * n, w); }

struct node {
	int dis, pos;
	friend bool operator < (const node &a, const node &b) { return a.dis > b.dis; }
};
priority_queue<node> q;

void dijkstra() {
	for (int i = 0; i <= n * (k + 1) + 100; i ++) dis[i] = 8e18;
	dis[s] = 0; q.push((node) { dis[s], s });
	while (!q.empty()) {
		int u = q.top().pos; q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int e = head[u]; e; e = g[e].next) {
			int v = g[e].to;
			if (dis[v] > dis[u] + g[e].w) {
				dis[v] = dis[u] + g[e].w;
				q.push((node) { dis[v], v });
			}
		}
	}
}

signed main() {
	cin >> n >> m >> k >> s >> t;
	for (int i = 1; i <= m; i ++) {
		int u, v, w; cin >> u >> v >> w;
		for (int j = 0; j <= k; j ++) {
			add_edge(u, v, w, j);
			add_edge(v, u, w, j);
		}
		for (int j = 0; j < k; j ++) {
			add_edge(u + j * n, v + (j + 1) * n, 0);
			add_edge(v + j * n, u + (j + 1) * n, 0);
		}
	}
	dijkstra();
	int ans = 8e18;
	for (int i = 0; i <= k; i ++)
		ans = min(ans, dis[t + i * n]);
	cout << ans << endl;
	return 0;
}

发表于 更新于 分类于 Disqus：
本文字数： 2k 阅读时长 ≈ 2 分钟
博客园 同步已开启

题目

（直接从洛谷网站上复制的div）

题目背景

狗哥做烂了最短路，突然机智的考了 Bosh 一道，没想到把 Bosh 考住了...你能帮 Bosh 解决吗？

题目描述

给定 nn 个点的带权有向图，求从 11 到 nn 的路径中边权之积最小的简单路径。

输入格式

第一行读入两个整数 nn，mm，表示共 nn 个点 mm 条边。 接下来 mm 行，每行三个正整数 xx，yy，zz，表示点 xx 到点 yy 有一条边权为z的边。

输出格式

输出仅包括一行，记为所求路径的边权之积，由于答案可能很大，因此狗哥仁慈地让你输出它模 99879987 的余数即可。

废话当然是一个数了w

//谢fyszzhouzj指正w

输入输出样例

输入 #1 
3 3
1 2 3 
2 3 3 
1 3 10
输出 #1 
9

说明/提示

对于 20%20\% 的数据，n≤10n\leq 10。

对于 100%100\% 的数据，n≤103n\leq 10^3，m≤106m\leq 10^6。边权不超过 10410^4。

题解

这道题注意点：乘积。一般有两种解决方式：

  • 对数
  • 记录路径

对数的话涉及到$\log$然后再还原到int可能会出现问题（反正我是失败了，我，菜），所以这里介绍第二种方法：直接记录路径，下面是具体分析。

记录路径

我们可以发现，在dijkstra的void里更新判断的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
#include <cstdio>
#include <queue>
#include <iostream> 
#include <cmath>
#define int long long

using namespace std;

const int maxn = 1000005;

int head[maxn];
int ecnt = 2, n, m;
double dis[maxn];
int pre[maxn];
int pre_weight[maxn];
bool vis[maxn];

struct edge {
	int to, next, w;
} g[maxn << 1];
void add_edge(int u, int v, int w) {
	g[ecnt] = (edge) { v, head[u], w };
	head[u] = ecnt ++;
}

struct node {
	double dis, pos;
	friend bool operator < (const node &a, const node &b) {
		return a.dis > b.dis;
	}
};
priority_queue<node> q;

void dijkstra() {
	for (int i = 1; i <= n; i ++) dis[i] = 8e18;
	dis[1] = 0; q.push((node) { 0, 1 });
	while (!q.empty()) {
		int u = q.top().pos; q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int e = head[u]; e != 0; e = g[e].next) {
			int v = g[e].to;
			if (dis[v] > dis[u] + log2(g[e].w)) {
				dis[v] = dis[u] + log2(g[e].w);
				q.push((node) { dis[v], v });
				pre[v] = u;
				pre_weight[v] = g[e].w;
			}
		}
	}
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i ++) {
		int x, y, z; cin >> x >> y >> z;
		add_edge(x, y, z);
		if (z == 0) {
			cout << 0 << endl;
			return 0;
		} 
	}
	dijkstra();
	int i = n;
	int ans = 1;
	while (pre[i] != 0) {
		ans = ans * pre_weight[i];
		ans = ans % 9987;
		i = pre[i];
	}
	cout << ans << endl; 
}

发表于 分类于 Disqus：
本文字数： 1.2k 阅读时长 ≈ 1 分钟
博客园 同步已开启

核心 - 图论的基本方程

问：在图中，$s\rightarrow t$最短路径是多少。

每一个点有一个$d(u)$（Distance），则对于所有边，有

算法解释

  • 上述方程可以展开写成$n$个方程构成的方程组，而Dijkstra算法则完成了这一过程。
  • Dijkstra方法可以理解为：从已知点出发，不断地从已知量计算未知量，因为是$\min$操作，我们每次都先取最小的值。
  • 具体如下图：

Ref 地址

关于堆优化

堆优化用在每次寻找当前dis数组中最小值的时候。所以我们需要维护一个小根堆，这将时间复杂度从$O(n^2)$降到了$O(n\log n)$

关于小根堆的实现

  1. 黑魔法：放入相反数，别忘了取的时候乘-1
  2. 正常人做法：priority_queue<int, vector<int>, greater<int> > q;
  3. 详见我的代码（直接在结构体当中重新定义运算符）

代码

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
int ecnt = 2; // 这也是黑魔法，直接0就行了
int n, m, k, s, t;
int head[150005], dis[150005], vis[150005];
struct edge { int to, next, w; } g[300010];
void add_edge(int u, int v, int w) { g[ecnt] = (edge) { v, head[u], w }; head[u] = ecnt ++; }

struct node {
	int dis, pos;
    // 前文提到的黑魔法
	friend bool operator < (const node &a, const node &b) { return a.dis > b.dis; }
};
priority_queue<node> q;

void dijkstra() {
	for (int i = 0; i <= n; i ++) dis[i] = 8e18;
	dis[s] = 0; q.push((node) { dis[s], s });
	while (!q.empty()) {
		int u = q.top().pos; q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int e = head[u]; e; e = g[e].next) {
			int v = g[e].to;
            // 图论基本方程
			if (dis[v] > dis[u] + g[e].w) {
				dis[v] = dis[u] + g[e].w;
				q.push((node) { dis[v], v });
			}
		}
	}
}

注：其中，单源最短路的源是s。