状压dp求解TSP问题

发表于 更新于 分类于

状压DP求解TSP问题

郊区旅游

img
AC代码：

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
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;
int n, m, r;
int ar[20];
int mp[205][205];
int dp[1<<16][20];
int x, y, z;

void floyd()
{
    for(int k = 1; k <= n; ++k)
    {
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
                mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &r);
    for(int i = 1; i <= r; ++i) scanf("%d", &ar[i]);

    memset(mp, 0x3f, sizeof(mp));
    memset(dp, 0x3f, sizeof(dp));

    for(int i = 1; i <= n; ++i) mp[i][i] = 0;

    while(m--)
    {
        scanf("%d%d%d", &x, &y, &z);
        mp[x][y] = mp[y][x] = z;
    }

    floyd();

    for(int i = 1; i <= r; ++i) dp[1<<(i-1)][i] = 0;

    for(int s = 0; s < (1<<r) - 1; ++s)
    {
        for(int i = 1; i <= r; ++i)
        {
            if(!(s >> (i - 1) & 1)) continue;
            for(int j = 1; j <= r; ++j)
            {
                if(s >> (j - 1) & 1) continue;
                if(mp[ar[i]][ar[j]] != inf)
                {
                    dp[s|(1<<(j-1))][j] = min(dp[s][i] + mp[ar[i]][ar[j]], dp[s|(1<<(j-1))][j]);
                }
            }
        }
    }

    int ans = 0x3f3f3f3f;

    for(int i = 1; i <= r; ++i)
    {
        ans = min(ans, dp[(1<<r) - 1][i]);
    }

    printf("%d\n", ans);
    return 0;
}

简单环

img
AC代码：

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll mod = 998244353;
int n, m, k;
bool mp[25][25];
int x, y;
ll dp[1100000][25]; // 2^20 = 1048576
ll ans[30];
int mi, len;

ll pow_mod(ll a, ll n)
{
    ll ans = 1;
    a %= mod;
    while(n)
    {
        if(n & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return ans;
}

int get_len(int x)
{
    int res = 0;
    while(x)
    {
        if(x&1) res++;
        x /= 2;
    }
    return res;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d", &x, &y);
        mp[x][y] = mp[y][x] = true;
    }

    for(int i = 1;i <= n; ++i)
    {
        dp[1<<(i-1)][i] = 1;
    }



    for(int s = 0; s < (1<<n); ++s) //枚举每一种状态
    {
        for(int i = 1; i <= n; ++i) //找到该种状态的最小点，用来标识路径
        {
            if((s>>(i-1))&1)
            {
                mi = i;
                break;
            }
        }

        len = get_len(s);

        for(int i = mi; i <= n; ++i) //枚举对于当前路径s时，现在要由哪一个点向外再次延长路径
        {
            if(!(s >> (i-1)&1)) continue; //这个点如果不在路径中则跳过
            for(int j = mi; j <= n; ++j) //枚举下一个点，确定了当前st是最小的点 那么就不要再去枚举比st小的点了 否则重复计算了
            {
                if(!mp[i][j]) continue; //于下一个点不连通
                if(mi == j) //下一个点是起点，形成环，记录答案
                {
                    if(len >= 3)
                        ans[len%k] = (ans[len%k] + dp[s][i]) % mod;
                }
                if(s >> (j - 1) & 1) continue; //这个点已经在路径里了
                int nxt = s | 1 << (j - 1);
                dp[nxt][j] = (dp[nxt][j] + dp[s][i]) % mod;
            }
        }
    }

    ll sum = 0;

    for(int i = 0; i < k; ++i)
    {
        printf("%lld\n", (ans[i] * pow_mod(2, mod - 2)) % mod);
    }

    //printf("%lld\n", (ans - m) / 2);
    //cout << (ans - m) / 2 << '\n';

    return 0;
}