UVa 1424 – Salesmen [DP]

Link

传送门

Mean

给定一个N个点M条边的无向图,一个人走出了一个路径,但这个路径有可能是不对的,例如图上并没有某条边。给你这个路径,让你再找出一条等长的路径,使得两条路径的距离最近。

路径的距离定义如下:每个点相同为0,不同为1.

Analysis

比较简单的dp,定义状态dp[i][j]为路径上第i个点走图上j号点时的最短路径距离,那么有递推方程:dp[i][j] = min(cur + dp[i-1][k]),k为j自己或者图上与j相连的点,cur是当前走的j号点是否与给定路径不同。

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 210, inf = 0x3f3f3f3f;
int n, m, s, v[maxn], dp[maxn][maxn];
vector<int> G[maxn];

int main()
{
    int T; cin >> T;
    while(T--) {
        cin >> n >> m;
        for(int i = 1; i <= n; ++i) {
            G[i].clear();
            G[i].push_back(i);
        }
        for(int i = 0; i < m; ++i) {
            int x, y; cin >> x >> y;
            G[x].push_back(y);
            G[y].push_back(x);
        }
        cin >> s;
        for(int i = 1; i <= s; ++i)
            cin >> v[i];
        memset(dp, inf, sizeof dp);
        for(int i = 1; i <= n; ++i)
            dp[1][i] = i != v[1];
        for(int i = 2; i <= s; ++i) {
            for(int j = 1; j <= n; ++j) {
                int cur = j != v[i];
                for(auto &k : G[j])
                    dp[i][j] = min(dp[i][j], cur + dp[i-1][k]);
            }
        }
        cout << *min_element(dp[s] + 1, dp[s] + n + 1) << endl;
    }
    return 0;
}

欢迎留言