P3057 题解
liangbowen
·
·
题解
前言
题目传送门
\color{red}{see}\space \color{green}{in}\space \color{blue}{my}\space \color{purple}{blog}
在学校比赛时遇到了这一题，写一篇题解纪念一下。
本题是最短路好题。
思路
此题明显是最短路。
我们需要求任意两点的最短路的最大值，即全源最短路。
本题共有 n^2 个点，如果跑 Floyd 时间复杂度是 O(n^6)，非常极限，不是本题正解。
但是，我又不会写 Johnson 全源最短路，怎么办呢?
每个点朝四周建边，容易发现，边的数量不超过 4 \times n^2。
想到这里，明显可以跑 n^2 次 dijkstra 实现，因为当边数较小时，跑多次 dijkstra 会比 Floyd 快。
此处 dijkstra 是使用优先队列实现。
那么就很容易写出代码了。
思路总结
-
读入数据。
-
每个点朝四周建边。
-
写一个 dijkstra 的模版。
-
统计最大值，输出。
代码
最短路模版没有强制要求，按照自己的习惯写 dijkstra 当然可以。
还有一个小细节：边数 m 最多有多少？
```cpp
#include <iostream>
#include <cstdio>
#include <queue>
#define N 905
#define M 7205
using namespace std;
int n, nn, A, B;
int dict[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool a[35][35];
struct Node
{
int now, nxt, w;
}e[M];
int head[N], cur;
void add(int x, int y, int k)
{
e[++cur].now = y;
e[cur].nxt = head[x];
e[cur].w = k;
head[x] = cur;
}
struct Dis
{
int pos, len;
bool operator <(const Dis &t) const
{
return len > t.len;
}
}dis[N];
bool vis[N];
int dijkstra(int first)
{
priority_queue <Dis> Q;
for (int i = 1; i <= nn; i++) dis[i].pos = i, dis[i].len = 2147483647, vis[i] = false;
dis[first].len = 0;
Q.push(dis[first]);
while (!Q.empty())
{
int topi = Q.top().pos;
Q.pop();
if (vis[topi]) continue;
vis[topi] = true;
for (int i = head[topi]; i; i = e[i].nxt)
if (dis[topi].len + e[i].w < dis[e[i].now].len)
{
dis[e[i].now].len = dis[topi].len + e[i].w;
Q.push(dis[e[i].now]);
}
}
//此处有是惟一与普通模版不同的地方，需要找出最大值。
int maxn = 0;
for (int i = 1; i <= nn; i++) maxn = max(maxn, dis[i].len);
return maxn;
}
void Input()
{
scanf("%d%d%d", &n, &A, &B);
nn = n * n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
char x;
cin >> x;
if (x == '(') a[i][j] = true;
}
}
void get_edge()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 0; k < 4; k++)
{
int x = i + dict[k][0], y = j + dict[k][1];
if (!(1 <= x && x <= n && 1 <= y && y <= n)) continue;
int t1 = n * (i-1) + j, t2 = n * (x-1) + y;
if (a[i][j] == a[x][y]) add(t1, t2, A);
else add(t1, t2, B);
}
}
void solve()
{
int maxn = 0;
for (int i = 1; i <= nn; i++) maxn = max(maxn, dijkstra(i));
printf("%d", maxn);
}
int main()
{
Input();
get_edge();
solve();
return 0;
}
```