codevs 2597 团伙

S 城现有两座监狱，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c 的冲突事件。
每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
在详细考察了N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是少？

输入描述 Input Description

第一行为两个正整数N 和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。

接下来的M 行每行为三个正整数aj，bj，cj，表示aj 号和bj 号罪犯之间存在仇恨，其怨气值为cj。数据保证，且每对罪犯组合只出现一次。

输出描述 Output Description

共1 行，为Z 市长看到的那个冲突事件的影响力。如果本年内监狱

中未发生任何冲突事件，请输出0。

样例输入 Sample Input

4 6

1 4 2534

2 3 3512

1 2 28351

1 3 6618

2 4 1805

3 4 12884

样例输出 Sample Output

3512

数据范围及提示 Data Size & Hint

罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是3512（由2 号和3 号罪犯引发）。其他任何分法都不会比这个分法更优。

【数据范围】

对于30%的数据有N≤ 15。

对于70%的数据有N≤ 2000，M≤ 50000。

对于100%的数据有N≤ 20000，M≤ 100000。

题解

对于 n 个点，这里使用了长度为 n * 2 的 fa 数组。例如当 n = 4 时。

黑色数字时数组下标，白字时数组内容。

对于例子：

4 3
1 2 9
1 3 8
2 3 7

首先读入数据，并按照仇恨值从大到小排序。
从仇恨值最大的 1 2 9 开始。
看 1 2 是否再同一个集合中，如果再则输出这时的仇恨值 9。
如果不再则执行：

1 2	fa[getfa(ps[i].x+n)] = getfa(ps[i].y); fa[getfa(ps[i].y+n)] = getfa(ps[i].x);

就是

下标 5 （就是 x + n）变成了 2，下标 6 变成了 1。

再看 1 3 8
1 3 再不同集合
在执行并集操作

这次把下标 3 变成了 3，下标 7 变成了 2。

再看 2 3 7
这是 2 和 3 再同一个集合内，说明 2 和 3 不可避免的会分到一个监狱，所以输出最大仇恨值 7。

AC 代码

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 20004, maxm = 100005;
int fa[maxn<<1];

struct p {
	int x, y, v;
}ps[maxm];

bool operator < (const p &a, const p &b) {
	return a.v > b.v;
}

int getfa(int x) {
	return fa[x] == x? x : fa[x]=getfa(fa[x]);
}

int main() {
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) 
		cin >> ps[i].x >> ps[i].y >> ps[i].v;
	for (int i = 1; i <= n<<1; i++) fa[i] = i;
	sort(ps, ps+m);
	for (int i = 0; i < m; i++) {
		if (getfa(ps[i].x) == getfa(ps[i].y)) {
			cout << ps[i].v << endl;
			return 0;
		}
		fa[getfa(ps[i].x+n)] = getfa(ps[i].y);
		fa[getfa(ps[i].y+n)] = getfa(ps[i].x);
	}
	cout << 0 << endl;
}

codevs 1001 舒适的路线

2019-09-30

刷题

输入描述 Input Description
输出描述 Output Description
样例输入 Sample Input
样例输出 Sample Output
数据范围及提示 Data Size & Hint

题解

题目描述 Description

Z小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。
Z小镇附近共有
N(1<N≤500)个景点（编号为1,2,3,…,N），这些景点被M（0<M≤5000）条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。也许是为了保护该地的旅游资源，Z小镇有个奇怪的规定，就是对于一条给定的公路Ri，任何在该公路上行驶的车辆速度必须为Vi。频繁的改变速度使得游客们很不舒服，因此大家从一个景点前往另一个景点的时候，都希望选择行使过程中最大速度和最小速度的比尽可能小的路线，也就是所谓最舒适的路线。

Leetcode weekly contest 156 穿过迷宫的最少移动次数 Minimum Moves to Reach Target with Rotations

2019-09-29

刷题

解答

你还记得那条风靡全球的贪吃蛇吗？

我们在一个 n*n 的网格上构建了新的迷宫地图，蛇的长度为 2，也就是说它会占去两个单元格。蛇会从左上角（(0, 0) 和 (0, 1)）开始移动。我们用 0 表示空单元格，用 1 表示障碍物。蛇需要移动到迷宫的右下角（(n-1, n-2) 和 (n-1, n-1)）。

每次移动，蛇可以这样走：

如果没有障碍，则向右移动一个单元格。并仍然保持身体的水平／竖直状态。
如果没有障碍，则向下移动一个单元格。并仍然保持身体的水平／竖直状态。
如果它处于水平状态并且其下面的两个单元都是空的，就顺时针旋转 90 度。蛇从（(r, c)、(r, c+1)）移动到（(r, c)、(r+1, c)）。

如果它处于竖直状态并且其右面的两个单元都是空的，就逆时针旋转 90 度。蛇从（(r, c)、(r+1, c)）移动到（(r, c)、(r, c+1)）。

返回蛇抵达目的地所需的最少移动次数。

如果无法到达目的地，请返回 -1。

示例 1：

输入：grid = [[0,0,0,0,0,1],
               [1,1,0,0,1,0],
               [0,0,0,0,1,1],
               [0,0,1,0,1,0],
               [0,1,1,0,0,0],
               [0,1,1,0,0,0]]
输出：11
解释：
一种可能的解决方案是 [右, 右, 顺时针旋转, 右, 下, 下, 下, 下, 逆时针旋转, 右, 下]。

示例 2：

输入：grid = [[0,0,1,1,1,1],
               [0,0,0,0,1,1],
               [1,1,0,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,0]]
输出：9

提示：

2 <= n <= 100
0 <= grid[i][j] <= 1
蛇保证从空单元格开始出发。

解答

广度优先搜索。需要导入 queue 模块。
定义三维数组，mp 记录蛇走过的所有位置，任意位置，只搜索一次。
先取 grid 的行数 xl，列数 yl。
mp 定义为 xl 行，yl 列，每个元素是二元组。初始全为 0。

定义蛇的位置用（x, y, z)三元组表示，是蛇最右、最上的格子的坐标为 x，y，蛇水平时，z 为 0，蛇竖直时，z 为 1。那么蛇最初位置就表示为 (0, 0, 0)，重点位置表示为(xl-1, yl-2, 0)。

再看蛇的位置转换：

当蛇水平时
1. 向右移动：条件是（x,y+2）没有障碍
2. 向下移动：条件是（x+1,y）、（x+1,y+1）都没有障碍
3. 顺时针旋转 90°：条件与 2. 相同
当蛇竖直时
1. 向右移动：条件是（x,y+1）、（x+1,y+1）都没有障碍
2. 向下移动：条件是（x+2,y）没有障碍
3. 逆时针旋转 90°：条件与 1. 相同

AC 代码

import queue
class Solution:

    def minimumMoves(self, grid: List[List[int]]) -> int:
        x = 0
        y = 0
        xl = len(grid)
        yl = len(grid[0])
        mp = [[[0,0] for j in range(yl)] for i in range(xl)]
        q = queue.Queue()
        q.put((0, 0, 0, 0))
        mp[0][0][0] = 1
        while not q.empty():
            x, y, z, s = q.get()
            if z == 0:
                if y + 2 < yl and grid[x][y+2] == 0 and mp[x][y+1][0] == 0:
                    if x == xl - 1 and y + 1 == yl - 2:
                        return s + 1
                    q.put((x, y+1, 0, s+1))
                    mp[x][y+1][0] = 1
                if x + 1 < xl and y + 1 < yl and grid[x+1][y] == 0 and grid[x+1][y+1] == 0:
                    if x+1 == xl - 1 and y == yl - 2:
                        return s + 1
                    if mp[x+1][y][0] == 0:
                        q.put((x+1, y, 0, s+1))
                        mp[x+1][y][0] = 1
                    if mp[x][y][1] == 0:
                        q.put((x, y, 1, s+1))
                        mp[x][y][1] = 1
            if z == 1:
                if x + 2 < xl and grid[x+2][y] == 0 and mp[x+1][y][1] == 0:
                    q.put((x+1, y, 1, s+1))
                    mp[x+1][y][1] = 1
                if x + 1 < xl and y + 1 < yl and grid[x+1][y+1] == 0 and grid[x][y+1] == 0:
                    if mp[x][y+1][1] == 0:
                        q.put((x, y+1, 1, s+1))
                        mp[x][y+1][1] = 1
                    if mp[x][y][0] == 0:
                        q.put((x, y, 0, s+1))
                        mp[x][y][0] = 1
        return -1