把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

HDU 3001 Travelling
题目大意：一个图，n个节点m条边，n不超过10，每条边都有长度，每个节点最多去两次，求把所有节点去过一次需要最少走多少距离。

解：

n不超过10，每个节点去两次，相当于可以转化成每个节点都有两个，但是我只能去完第一个才去第二个，问题轻松解决。
然后在hdu的32MB内存限制下直接MLE了，不过我还是坚信这种做法是能过的。

不过问题在于每个点多能去一次状态的数量就直接上升了一个次方，非常不划算。于是想到了用三进制来保存状态，其他就和普通的TSP一样了。
状态数量是3^10，和2^20比起来还是很划算的，而且常数也稳定在10，重要的是hdu能跑过去。
还有个很坑的地方，两个点之间可能有很多条边，要取距离最短的那条作为距离。
TSP的状压dp遍历可以直接顺序上升地写，原因是一个状态转移到下一个状态的时候一定是当前的状态上加了一个值，所以转移去的状态大小一定是大于当前状态的，实现了无后效性。

代码

代码
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 1000005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define inc(i,a,n) for(ll i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;
#define endl '\n'using namespace std;
ll dis[11][11];
ll bei[11];
ll dp[60000][11];
ll getbs(int state, int wei) {
    int res = state / bei[wei];
    res %= 3;
    return res;
}
bool judge(int state,int wei) {
    inc(i, 0, wei) {
        if (getbs(state, i) == 0)return false;
    }
    return true;
}
int main() {
    cfast;
    bei[0] = 1;
    inc(i, 1, 11) {
        bei[i] = bei[i - 1] * 3;
       // cout << bei[i] << " ";    }
    int n, m;
    while (cin >> n >> m) {
        inc(i, 0, n) {
            inc(j, 0, n) {
                dis[i][j] = 1e18;
            }
        }
        while (m--) {
            int a, b;
            ll d;
            cin >> a >> b >> d;
            a--;
            b--;
            dis[a][b] = min(dis[a][b],d);
            dis[b][a] = min(dis[b][a],d);
        }
        ll ans = 1e18; 
        inc(i, 0, bei[n]) {
            inc(j, 0, n) {
                dp[i][j] = 1e18;
            }
        }
        inc(j, 0, n) {
            dp[bei[j]][j] = 0;
        }
        inc(i, 0, bei[n]) {
            inc(j, 0, n) {
                if (getbs(i, j) == 0)continue;
                inc(k, 0, n) {
                    if (j == k)continue;
                    if (getbs(i, k) == 2)continue;
                    if (dis[j][k] == 1e18)continue;
                    dp[i + bei[k]][k] = min(dp[i + bei[k]][k], dp[i][j] + dis[j][k]);
                  //  cout << "dp." << i + bei[k] << "." << k << " = " << dp[i + bei[k]][k] << endl;                    if (judge(i + bei[k], n) == 1)ans = min(ans, dp[i + bei[k]][k]);
                }
            }
        }
        if (ans != 1e18)cout << ans << endl;
        else cout << "-1" << endl;
    }

}

代码：（增点）
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 1000005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define inc(i,a,n) for(ll i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;
#define endl '\n'using namespace std;
int dp[1 << 20][20];
int dis[20][20];
int main() {
    cfast;
    int n, m;
    while (cin >> n >> m) {
        memset(dis, 0, sizeof(dis));
        for (int i = 0; i < (1<<(2*n)); i++) {
            for (int j = 0; j < 2*n; j++) {
                if (i == (1 << j))dp[i][j] = 0;
                else dp[i][j] = 1e9;
            }
        }
        while (m--) {
            int a, b;
            int d;
            cin >> a >> b >> d;
            a--;
            b--;
            dis[a][b] = d;
            dis[b][a] = d;
            dis[(a + n) % (2*n)][(b + n) % (2*n)] = d;
            dis[(b + n) % (2*n)][(a + n) % (2*n)] = d;
            dis[a][(b + n) % (2 * n)] = d;
            dis[(b + n) % (2 * n)][a] = d;
            dis[(a + n) % (2 * n)][b] = d;
            dis[b][(a + n) %( 2 * n)] = d;
        }
        int ans = 1e9;
      //  cout << dis[0][1] << endl;;        for (int i = 0; i < (1 << 2 * n); i++) {
           
            for (int j = 0; j < 2 * n; j++) {
                if (i % (1 << n) == (1 << n) - 1) {
                //   cout << i << " * ";                    ans = min(ans, dp[i][j]);
                    continue;
                }
                if ((i & (1 << j)) == 0)continue;
                for (int k = 0; k < 2 * n; k++) {
                    if ((i & (1 << k)) != 0)continue;
                    if (dis[j][k]==0)continue;
                    if (k >= n && (i & (1 << (k - n)) == 0))continue;
                  //  cout << i << " * ";                    dp[i + (1 << k)][k] = min(dp[i + (1 << k)][k], dp[i][j] + dis[j][k]);
                 //   if(dp[i+(1<<k)][k]!=1e9)cout << "dp." <<getbin( i + (1 << k)) << "."<<k+1 << " = " << dp[i + (1 << k)][k] << endl;                }
                
            }
        }
        cout << ans << endl;
    }

}