【题解】EOJ-3479 现任总统的巡游

题目

http://acm.ecnu.edu.cn/problem/3479/

题意

在一个有向图中,求从结点 1 出发经过结点 2 最后回到结点 1 最少经过几个点。

题解

  • 观察 1:$1 \rightarrow 2$ 和 $2 \rightarrow 1$ 来回两趟各自不会经过同一个点。
  • 观察 2:重复利用的点在路径的交叉处,可能是一个点,也可能是一条路径。
  • $dp[x][y]$ 为从 $1$ 出发,两个点分别走正向边到 $x$ 以及走反向边到 $y$,经过最少的点的个数。
  • 设原图为 $G(V,E)$,$dist[i][j]$ 为 $i$ 到 $j$ 最短路的长度,建一个新图 $G’(V’,E’)$ 用于状态转移,$dp[x][y]$ 对应结点 $(x,y)$。
  • $\forall t \in V, \forall (u,v) \in E: ((u, t), (v, t)) \in E’ \land ((t, v), (t, u)) \in E’$,对应的是两个点中的某个点在原图上走一步,所以边权等于原边权,此时还没有考虑点重复利用的情况。
  • 考虑点的重复利用 $(a \neq b)$
    • 情况 1:重复利用的恰好是一个点。$(a, b)$ 与 $(a,a)$ 和 $(b,b)$ 连一条长度为 $dist[a][b]-1$ 的边。
    • 情况 2:重复利用的是一条路径。$(a,b)$ 与 $(b,a)$ 连一条长度为 $dist[a][b]-1$ 的边。
    • 为什么要分两种情况呢?因为害怕从 $(a,a)$ 到 $(a,a)$ 之间有负权边。也可以不分开讨论,只要那条 -1 的边不会重复经过就行了。
  • 正确性如何保证?对于所有可能的路径交叉,都存在一种方案能够转移到。把交叉的部分看做是两个点交换位置,而两个点以及之间的点都重复利用了一次。同时根据最开始的观察,不可能有点被重复利用超过两次,因此没有后效性。
  • 最后就是求 $(1,1)$ 到 $(2,2)$ 的最短路,代码中用的是 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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args<< " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 100 + 5;
int d[maxn][maxn], f[maxn][maxn];
bool vis[maxn][maxn];
int n, m;

struct P {
int u, v;
};
queue<P> q;

void ins(int u, int v, int nxt) {
if (nxt < f[u][v]) {
f[u][v] = nxt;
if (!vis[u][v]) q.push({u, v});
vis[u][v] = true;
}
}

int main() {
cin >> n >> m;
memset(d, 0x3f, sizeof d); // 没有将对角线初始化为 0,防止负权边出现
memset(f, 0x3f, sizeof f);
FOR (_, 0, m) {
int u, v;
cin >> u >> v;
d[--u][--v] = 1;
}
FOR (k, 0, n)
FOR (i, 0, n)
FOR (j, 0, n)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
f[0][0] = 1;
q.push({0, 0});
while (!q.empty()) {
int u = q.front().u, v = q.front().v; q.pop();
vis[u][v] = false;
FOR (i, 0, n) {
ins(i, v, d[u][i] + f[u][v]);
ins(u, i, d[i][v] + f[u][v]);
}
int dist = d[u][v] + f[u][v] - 1;
ins(v, u, dist);
ins(u, u, dist);
ins(v, v, dist);
}
cout << f[1][1] << endl;
}

再贴一份稍作修改后的 ultmaster 的代码。

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 <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int, int> P;

struct HeapNode {
P u; int d;
bool operator < (const HeapNode& x) const {
return d > x.d;
}
};

const int N = 2e2 + 10;
const int INF = 1e9 + 7;
int n, m, done[N][N], dis[N][N];
int mat[N][N];
priority_queue<HeapNode> q;

void relax(int x, int y, int new_dis) {
if (x == y) --new_dis;
if (new_dis < dis[x][y]) {
dis[x][y] = new_dis;
q.push({P(x, y), dis[x][y]});
}
}

int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
mat[i][j] = dis[i][j] = INF;
while (m--) {
int u, v; cin >> u >> v;
mat[u][v] = 1;
}

for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);

dis[1][1] = 1;

q.push({P(1, 1), 1});
while (!q.empty()) {
HeapNode x = q.top(); q.pop();
P u = x.u;
if (done[u.fi][u.se]) continue;
done[u.fi][u.se] = 1;

for (int v = 1; v <= n; ++v) {
relax(v, u.se, dis[u.fi][u.se] + mat[u.fi][v]);
relax(u.fi, v, dis[u.fi][u.se] + mat[v][u.se]);
}
if (u.se != u.fi)
relax(u.se, u.fi, dis[u.fi][u.se] + mat[u.fi][u.se] - 1);
}
printf("%d\n", dis[2][2]);
}