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
| #include<iostream> #include<vector> #include<string>
using namespace std;
vector<vector<int>> weights = { {0,2,2,3,1,4},{2,0,1,5,2,3},{2,1,0,2,1,4},{3,5,2,0,6,2},{1,2,1,6,0,1} ,{4,3,4,2,1,0} }; const int N = 1000; int m[N][N], s[N][N]; vector<string> res; int get_weight(int i, int j, int k,int n) { if (k < n) { return weights[i][j] + weights[j][k] + weights[k][i]; } }
void convex_polygon_optimal(int n) { memset(m, 0, sizeof m); memset(s, 0, sizeof s); for (int i = 0; i < n; i++) { m[i][i] = 0; s[i][i] = 0; } for (int r = 2; r < n; r++) { for (int i = 1; i < n - r + 1; i++) { int j = (i + r - 1) % n; m[i][j] = m[(i + 1) % n][j] + get_weight(i - 1, i, j, n); s[i][j] = i; for (int k = i + 1; k < j; k++) { int t = m[i][k] + m[(k + 1) % n][j] + get_weight(i - 1, k, j, n); if (t < m[i][j]) { m[i][j] = t; s[i][j] = k; } } } } }
void trace_back(int i, int j) { if (i == j) { return; } else { trace_back(i, s[i][j]); trace_back(s[i][j] + 1, j); res.insert(res.begin(), "v" + to_string((i - 1)) + ",v" + to_string(j) + ",v" + to_string(s[i][j])); } } int main() { int n = weights.size(); convex_polygon_optimal(n); trace_back(1,5); for (int i = 0; i < res.size(); i++) { cout << res[i] << " "; } return 0; }
|