【UVA1057】Routing

题面

洛谷

题解

有一个比较好想的dp就是\(f_{i,j}\)表示第一个点在\(i\)，第二个点在\(j\)的最小点数，但是直接搞不好转移。
考虑建出反图，那么\(j\)表示在反图上的点\(j\)其实是和正图上的是一样的。

这样子的话我们枚举出边转移：
\[f[v][u2]=f[u1][u2]+[u2!=v],((u1,v)\in G)\\f[u1][v]=f[u1][u2]+[u1!=v],((u2,v)\in G')\]

然而我们交换两条路径时发现点数会算多，这种情况我们用另一种方式转移：
\[f[u2][u1]=min(f[u2][u1],f[u1][u2]+dis[u1][u2]-1)\]
其中\(dis[u1][u2]\)表示\(u1,u2\)间的最短路，可以用\(floyd\)求出。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int INF = 1e9;
const int MAX_N = 105;
int N, M;
int f[MAX_N][MAX_N], dis[MAX_N][MAX_N];
vector<int> G[MAX_N], E[MAX_N];
bool inq[MAX_N][MAX_N];
void spfa() {
    queue<pair<int, int> > que;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) f[i][j] = INF;
    f[1][1] = 1, inq[1][1] = 1, que.push(make_pair(1, 1));
    while (!que.empty()) {
        pair<int, int> p = que.front(); que.pop();
        int x1 = p.first, x2 = p.second;
        for (auto v : G[x1])
            if (f[v][x2] > f[x1][x2] + (v != x2)) {
                f[v][x2] = f[x1][x2] + (v != x2);
                if (!inq[v][x2]) inq[v][x2] = 1, que.push(make_pair(v, x2));
            }
        for (auto v : E[x2])
            if (f[x1][v] > f[x1][x2] + (v != x1)) {
                f[x1][v] = f[x1][x2] + (v != x1);
                if (!inq[x1][v]) inq[x1][v] = 1, que.push(make_pair(x1, v));
            }
        if (x1 != x2 && f[x2][x1] > f[x1][x2] + dis[x1][x2] - 1) {
            f[x2][x1] = f[x1][x2] + dis[x1][x2] - 1;
            if (!inq[x2][x1]) inq[x2][x1] = 1, que.push(make_pair(x2, x1));
        }
        inq[x1][x2] = 0;
    }
}
int main () {
    int Case = 0;
    while (scanf("%d %d", &N, &M) != EOF) {
        if (!N && !M) break;
        printf("Network %d\n", ++Case);
        for (int i = 1; i <= N; i++) G[i].clear(), E[i].clear();
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++) dis[i][j] = INF;
        for (int i = 1; i <= N; i++) dis[i][i] = 0;
        for (int i = 1; i <= M; i++) {
            int u, v; scanf("%d %d", &u, &v);
            dis[u][v] = 1, G[u].push_back(v), E[v].push_back(u);
        }
        for (int k = 1; k <= N; k++)
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= N; j++)
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
        if (dis[1][2] == INF || dis[2][1] == INF) puts("Impossible");
        else spfa(), printf("Minimum number of nodes = %d\n", f[2][2]);
        putchar('\n');
    }
    return 0;
}