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

Posted on In Disqus:

题目

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]);
}