题解 P1902 【刺杀大使】
Social_Zhao
2019-07-07 10:41:17
## Part 0 前言
这是你没有见过的船新解法。
请自动忽略算法标签。
------
## Part 1 考虑正解——二分+bfs
我们在题面中看到了**最大值最小** 这五个字。
很容易就想到了二分答案。
然鹅我的``dfs``挂了，所以我就写了``bfs``，阿掉了。
本来就是很裸的做法，限于篇幅，这里就无需赘述了。
```cpp
#include<bits/stdc++.h>
using namespace std;
int get()
{
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
const int MaxN = 1005;
const int inf = 0x3f3f3f3f;
const int dx[5] = {0, 1, 0, -1, 0};
const int dy[5] = {0, 0, 1, 0, -1};
int p[MaxN][MaxN], vis[MaxN][MaxN];
int n, m;
int l = inf, r = -inf, mid, ans, f;
bool bfs(int x, int y, int maxn) //判断mid是否可行的bfs
{
queue<pair<int, int> > q;
q.push(make_pair(x, y)); //STL里的pair，个人认为要方便一些
vis[x][y] = 1;
while(q.size()) { //以下就是bfs板子
int xx = q.front().first;
int yy = q.front().second;
q.pop();
for(int i = 1; i <= 4; i++) {
int nx = xx + dx[i];
int ny = yy + dy[i];
if(nx < 1 || nx > n || yy < 1 || yy > m || vis[nx][ny] || p[nx][ny] > maxn)
continue; //不可行（越界、已访问、伤害过大）的直接跳过
vis[nx][ny] = 1;
if(nx == n) return 1; //到了，返回1
else q.push(make_pair(nx, ny));
}
}
return 0; //没有搜到，返回0
}
int main()
{
n = get(), m = get();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
p[i][j] = get();
r = max(r, p[i][j]);
l = min(l, p[i][j]);
}
}
while(l <= r) { //二分答案模板
mid = (l + r) >> 1;
f = 0;
memset(vis, 0, sizeof(vis)); //重置数组
if(bfs(1, 1, mid)) r = mid - 1, ans = mid; //如果这个mid可行，说明可能还能再小，于是更新答案 + 缩小范围
else l = mid + 1; //mid此不可行，说明不可能再小，也缩小范围，不更新答案
}
printf("%d", ans);
return 0;
}
```
## Part 2 新解法
二分这种算法对题中的``p[i][j]``的依赖较严重。如果加强数据，改到$10^9$怎么办呢？
这样就需要一个靠``n``、``m``吃饭的算法了
在看这个解法前，您需要一些图论知识
让我们把样例画成一张图：（暂不带权）
这个图得到的方法：
设点号为``k``，这个点是``x``行``y``列。
则有：$k=(x-1) \times m + y$
我们的任务是从第一行到第四行，求出经过的最大点权最小（有一点绕）
首先我们需要把点权转成边权：
仔细地钻研这句话：
> 最大点权最小
解读：
- 根据最大，我们可以想到如果我们要点转边，两点之间的边权应为两端点的点权最大值。
- 根据这个边转点的原理，可以得到这一张图：
- 根据最小，得出：我们需要选择一些边来使第一行和最后一行连通，这些边的权尽量小
现在我的思路就显而易见了：**MST（最小生成树）**
但是又不是裸的最小生成树。我们不需要选择``n-1``条边，只需要使首尾两行连通。
所以我们选择``Kruskal``算法，用并查集维护：
按照题面，第一行和最后一行的边权都是``0``，中间又不可能出现负权，所以我们的算法会首先选出这些边，因此可以认为这些点从**一开始就是连通**的，并且可以认为，将这两行都连通，就等价于将分别位于这两行上的任意两点连通。为了简便，我们将第一个点和第八个点连通。如图：红边表示已选边，黑边未选边
现在按照生成树算法，开始选其他边
第一步，选择目前最小的未选边——在``5``和``7``之间，边权为``2``的边：
第二步、第三步，选出目前边权最小的边，分别是——在``3``和``5``之间，边权为``3``的边、在``1``到``3``之间，边权为``3``的边（节约篇幅，一并画出）：
这时候，我们愉快地发现，``1``号和``8``号已经连通了。算法结束，答案为``3``。
上代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int get()
{
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
const int MaxN = 1005;
const int inf = 0x3f3f3f3f;
int p[MaxN][MaxN];
int n, m, maxn = -inf;
struct Edge {
int u, v, w;
} edge[10000005];
int k = 0;
int fa[10000005];
int MAP(int x, int y) { return (x - 1) * m + y; } //此函数用于求（x，y）在图中的编号
int find(int x) { return (x == fa[x]? x : fa[x] = find(fa[x])); } //一行并查集
bool cmp(Edge a, Edge b) { return a.w < b.w; } //一行cmp
void kruskal() //克鲁斯卡尔算法:
{
sort(edge + 1, edge + k + 1, cmp); //首先将边按权值排序
int st = MAP(1, 1); //指定一个开始点：第一个
int ed = MAP(n, m); //指定一个结束点：最后一个
for(int i = 1; i <= k; i++) { //枚举边：
int u = edge[i].u;
int v = edge[i].v;
int x = find(u), y = find(v); //取出u、v所在连通块
if(x != y) //若在同一连通块，我们就算去合并也没有多大意义，这样可以稍微节省时间
{
maxn = max(maxn, edge[i].w); //更新最大边权
fa[x] = fa[y]; //将两边连通
if(find(st) == find(ed)) return; //如果开始点和结束点连通了，说明可以退出了
}
}
}
int main()
{
n = get(), m = get();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
p[i][j] = get();
fa[MAP(i, j)] = MAP(i, j); //在读入的时候顺便初始化并查集
}
}
//重点：连边
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int u = MAP(i, j); //这个点
int v1 = MAP(i, j + 1); //向右连边
int v2 = MAP(i + 1, j); //向下连边
//因为是无向图，只用向两个方向连边
//权值是两点权间的较小值
if(j + 1 <= m) edge[++k] = {u, v1, max(p[i][j], p[i][j + 1])}; //注意判断越界。
if(i + 1 <= n) edge[++k] = {u, v2, max(p[i][j], p[i + 1][j])};
}
}
/*
for(int i = 1; i <= k; i++) {
printf("%d %d %d\n", edge[i].u, edge[i].v, edge[i].w);
}
*/
kruskal(); //跑MST算法
printf("%d", maxn); //输出解
return 0;
}
```
## Part 3 后记
前者的时间：搜索的复杂度完全就是玄学（取决于数据）
关于后者的时间？
读入、连边、快排占据了绝大部分时间，克鲁斯卡尔是线性的（可以忽略不计）。稍微卡卡常还是能跑的很快的。
经过实测，后者比前者慢、空间大、代码长······那为什么还要这么做呢？
毕竟多思考一下总是好的。
注：因为是不按常理出牌的方法，可能会有锅（虽然正确性可以得到证明）。如果您发现了``HACK``的方法，或者有不懂的地方，请私信作者。