Giải bài tập toán 12 nâng cao hình họcb ai3

1. Industry Student Olympiad in IT & ACM/ICPC DST Team Notebook DST TEAM MEMBERS Hung Bui Hinh Le Viet Pham – – – [email protected] [email protected] [email protected] Faculty of Information Technology 2011 Group of HaUI Student Olympiad in IT & ACM/ICPC Website: http://olympic.fit-haui.edu.vn 1
2. THEORETIC ALGORITHM ........................................................................4 1) Number theoretic algorithm .......................................................................................................4 2) Gauss-Jordan ..............................................................................................................................6 3) Reduced Row Echelon Form ......................................................................................................7 4) Fast Fourier transform ................................................................................................................9 5) Simplex algorithm ....................................................................................................................10 6) Prime lower than N...................................................................................................................12 CHAPTER II: TỐI ƯU TỔ HỢP ......................................................................................................15 7) Dinic’s Algorithm.....................................................................................................................15 8) Min cost max-flow ...................................................................................................................16 9) Push relabel Ford-Fulkerson ....................................................................................................18 10) Min Cost Matching...................................................................................................................20 11) Max Bipartite Matching ...........................................................................................................22 12) Lát cắt trên đồ thị......................................................................................................................22 13) Graph Cut Inference .................................................................................................................23 14) Ford-Fulkerson .........................................................................................................................26 CHAPTER III: 1) GRAPH ......................................................................................................................26 GRAPH PRESENTATION ......................................................................................................26 a) Using Adjency List ...............................................................................................................26 b) Danh sách kề có trọng số ......................................................................................................27 2) GRAPH SEARCHING.............................................................................................................29 a) Depth First Search ................................................................................................................29 b) Breath First Search ...............................................................................................................30 3) FIND MIN PATH ....................................................................................................................32 a) Thuật toán FLOYD ...............................................................................................................32 b) Thuật toán DIJKSTRA .........................................................................................................33 c) DIJKSTRA using Adjancy List ............................................................................................34 4) Strong connected Component ..................................................................................................35 CHAPTER IV: 1) STRING .....................................................................................................................37 STRING MATCHING .............................................................................................................37 a) Knuth-Morris-Pratt ...............................................................................................................37 b) Boyer-More...........................................................................................................................39 CHAPTER V: DYNAMIC PROGRAMMING .................................................................................42 2
3. QUY HOẠCH ĐỘNG ĐIỂN HÌNH ...........................................................42 1) a) Dãy con đơn điệu dài nhất ....................................................................................................42 b) Longest Increasing Subsequence Code O(NlogN) ...............................................................43 c) Vali (B) .................................................................................................................................45 d) Biến đổi xâu: .........................................................................................................................47 e) Vali (A) .................................................................................................................................49 f) Nhân ma trận ............................................................................................................................51 g) Ghép cặp ...............................................................................................................................52 QUY HOẠCH ĐỘNG TRẠNG THÁI ....................................................................................53 2) a) 3) Trò chơi trên lưới ..................................................................................................................53 MỘT SỐ BÀI TOÁN QUY HOẠCH ĐỘNG BỔ XUNG ......................................................54 CHAPTER VI: GEOMETRY .............................................................................................................56 1) Convex Hull .............................................................................................................................56 2) Geometry Computation ............................................................................................................57 3) JavaGeometry ...........................................................................................................................62 4) Geometry 3D ............................................................................................................................64 5) Delaunay triangulation .............................................................................................................65 CHAPTER VII: SPECIAL DATA STRUCTURE ..............................................................................67 1) Binary index tree ......................................................................................................................67 2) Disjoint-Set...............................................................................................................................67 3) KD-Tree....................................................................................................................................67 4) SuffixArray...............................................................................................................................70 5) Disjoint-Set...............................................................................................................................72 6) Interval tree...............................................................................................................................73 3
4. THEORETIC ALGORITHM 1) Number theoretic algorithm // This is a collection of useful code for solving problems that // involve modular linear equations. Note that all of the // algorithms described here work on nonnegative integers.
include

include

include using namespace std; typedef vector VI; typedef pair PII; // return a % b (positive value) int mod(int a, int b) { return ((a%b)+b)%b; } // computes gcd(a,b) int gcd(int a, int b) { int tmp; while(b){a%=b; tmp=a; a=b; b=tmp;} return a; } // computes lcm(a,b) int lcm(int a, int b) { return a/gcd(a,b)*b; } // returns d = gcd(a,b); finds x,y such that d = ax + by int extended_euclid(int a, int b, int &x, int &y) { int xx = y = 0; int yy = x = 1; while (b) { int q = a/b; int t = b; b = a%b; a = t; t = xx; xx = x-q*xx; x = t; t = yy; yy = y-q*yy; y = t; } return a; } // finds all solutions to ax = b (mod n) VI modular_linear_equation_solver(int a, int b, int n) { int x, y; VI solutions; int d = extended_euclid(a, n, x, y); if (!(b%d)) { x = mod (x*(b/d), n); for (int i = 0; i < d; i++) solutions.push_back(mod(x + i*(n/d), n)); } return solutions; } // computes b such that ab = 1 (mod n), returns -1 on failure int mod_inverse(int a, int n) { int x, y; int d = extended_euclid(a, n, x, y); if (d > 1) return -1; 4
5. remainder theorem (special case): find z such that // z % x = a, z % y = b. Here, z is unique modulo M = lcm(x,y). // Return (z,M). On failure, M = -1. PII chinese_remainder_theorem(int x, int a, int y, int b) { int s, t; int d = extended_euclid(x, y, s, t); if (a%d != b%d) return make_pair(0, -1); return make_pair(mod(s*b*x+t*a*y,x*y)/d, x*y/d); } // Chinese remainder theorem: find z such that // z % x[i] = a[i] for all i. Note that the solution is // unique modulo M = lcm_i (x[i]). Return (z,M). On // failure, M = -1. Note that we do not require the a[i]'s // to be relatively prime. PII chinese_remainder_theorem(const VI &x, const VI &a) { PII ret = make_pair(a[0], x[0]); for (int i = 1; i < x.size(); i++) { ret = chinese_remainder_theorem(ret.first, ret.second, x[i], a[i]); if (ret.second == -1) break; } return ret; } // computes x and y such that ax + by = c; on failure, x = y =-1 void linear_diophantine(int a, int b, int c, int &x, int &y) { int d = gcd(a,b); if (c%d) { x = y = -1; } else { x = c/d * mod_inverse(a/d, b/d); y = (c-a*x)/b; } } int main() { // expected: 2 cout << gcd(14, 30) << endl; // expected: 2 -2 1 int x, y; int d = extended_euclid(14, 30, x, y); cout << d << " " << x << " " << y << endl; // expected: 95 45 VI sols = modular_linear_equation_solver(14, 30, 100); for (int i = 0; i < (int) sols.size(); i++) cout << sols[i] << " "; cout << endl; // expected: 8 cout << mod_inverse(8, 9) << endl; // expected: 23 56 // 11 12 int xs[] = {3, 5, 7, 4, 6}; int as[] = {2, 3, 2, 3, 5}; PII ret = chinese_remainder_theorem(VI (xs, xs+3), VI(as, as+3)); cout << ret.first << " " << ret.second << endl; ret = chinese_remainder_theorem (VI(xs+3, xs+5), VI(as+3, as+5)); cout << ret.first << " " << ret.second << endl; 5
6. -15 linear_diophantine(7, 2, 5, x, y); cout << x << " " << y << endl; } 2) Gauss-Jordan // // // // // // // // // // // // // // // Gauss-Jordan elimination with full pivoting. Uses: (1) solving systems of linear equations (AX=B) (2) inverting matrices (AX=I) (3) computing determinants of square matrices Running time: O(n^3) INPUT: a[][] = an nxn matrix b[][] = an nxm matrix OUTPUT: X = an nxm matrix (stored in b[][]) A^{-1} = an nxn matrix (stored in a[][]) returns determinant of a[][]
include

include

include using namespace std; const double EPS = 1e-10; typedef typedef typedef typedef vector VI; double T; vector VT; vector VVT; T GaussJordan(VVT &a, VVT &b) { const int n = a.size(); const int m = b[0].size(); VI irow(n), icol(n), ipiv(n); T det = 1; for (int i = 0; i < n; i++) { int pj = -1, pk = -1; for (int j = 0; j < n; j++) if (!ipiv[j]) for (int k = 0; k < n; k++) if (!ipiv[k]) if (pj == -1 || fabs(a[j][k]) > fabs(a[pj][pk])) { pj = j; pk = k; } if (fabs(a[pj][pk]) < EPS) { cerr << "Matrix is singular." << endl; exit(0); } ipiv[pk]; swap(a[pj], a[pk]); swap(b[pj], b[pk]); if (pj != pk) det *= -1; irow[i] = pj; icol[i] = pk; T c = 1.0 / a[pk][pk]; det *= a[pk][pk]; a[pk][pk] = 1.0; for (int p = 0; p < n; p) a[pk][p] *= c; for (int p = 0; p < m; p++) b[pk][p] *= c; for (int p = 0; p < n; p++) if (p != pk) { c = a[p][pk]; a[p][pk] = 0; for (int q = 0; q < n; q++) a[p][q] -= a[pk][q] * c; for (int q = 0; q < m; q++) b[p][q] -= b[pk][q] * c; 6
7. = n-1; p >= 0; p--) if (irow[p] != icol[p]) { for (int k = 0; k < n; k++) swap(a[k][irow[p]], a[k][icol[p]]); } return det; } int main() { const int n = 4; const int m = 2; double A[n][n] = { {1,2,3,4},{1,0,1,0},{5,3,2,4},{6,1,4,6} }; double B[n][m] = { {1,2},{4,3},{5,6},{8,7} }; VVT a(n), b(n); for (int i = 0; i < n; i++) { a[i] = VT(A[i], A[i] + n); b[i] = VT(B[i], B[i] + m); } double det = GaussJordan(a, b); // expected: 60 cout << "Determinant: " << det << endl; // expected: -0.233333 0.166667 0.133333 0.0666667 // 0.166667 0.166667 0.333333 -0.333333 // 0.233333 0.833333 -0.133333 -0.0666667 // 0.05 -0.75 -0.1 0.2 cout << "Inverse: " << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cout << a[i][j] << ' '; cout << endl; } // expected: 1.63333 1.3 // -0.166667 0.5 // 2.36667 1.7 // -1.85 -1.35 cout << "Solution: " << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) cout << b[i][j] << ' '; cout << endl; } } 3) Reduced Row Echelon Form // // // // // // // // // // Reduced row echelon form via Gauss-Jordan elimination with partial pivoting. This can be used for computing the rank of a matrix. Running time: O(n^3) INPUT: a[][] = an nxn matrix OUTPUT: rref[][] = an nxm matrix (stored in a[][]) returns rank of a[][]
include

include

include 7
8. double EPSILON = 1e-10; typedef double T; typedef vector VT; typedef vector VVT; int rref(VVT &a) { int n = a.size(); int m = a[0].size(); int r = 0; for (int c = 0; c < m; c++) { int j = r; for (int i = r+1; i < n; i++) if (fabs(a[i][c]) > fabs(a[j][c])) j = i; if (fabs(a[j][c]) < EPSILON) continue; swap(a[j], a[r]); T s = 1.0 / a[r][c]; for (int j = 0; j < m; j++) a[r][j] *= s; for (int i = 0; i < n; i++) if (i != r) { T t = a[i][c]; for (int j = 0; j < m; j++) a[i][j] -= t * a[r][j]; } r++; } return r; } int main(){ const int n = 5; const int m = 4; double A[n][m] = { {16,2,3,13},{5,11,10,8},{9,7,6,12},{4,14,15,1},{13,21,21,13} }; VVT a(n); for (int i = 0; i < n; i++) a[i] = VT(A[i], A[i] + n); int rank = rref (a); // expected: 4 cout << "Rank: " << rank << endl; // expected: 1 0 0 1 // 0 1 0 3 // 0 0 1 -3 // 0 0 0 2.78206e-15 // 0 0 0 3.22398e-15 cout << "rref: " << endl; for (int i = 0; i < 5; i++){ for (int j = 0; j < 4; j++) cout << a[i][j] << ' '; cout << endl; } } 8
9. transform // // // // // // // // // // // // Convolution using the fast Fourier transform (FFT). INPUT: a[1...n] b[1...m] OUTPUT: c[1...n+m-1] such that c[k] = sum_{i=0}^k a[i] b[k-i] Alternatively, you can use the DFT() routine directly, which will zero-pad your input to the next largest power of 2 and compute the DFT or inverse DFT.
include

include

include using namespace std; typedef typedef typedef typedef long double DOUBLE; complex COMPLEX; vector VD; vector VC; struct FFT { VC A; int n, L; int ReverseBits(int k) { int ret = 0; for (int i = 0; i < L; i++) { ret = (ret << 1) | (k & 1); k >>= 1; } return ret; } void BitReverseCopy(VC a) { for (n = 1, L = 0; n < a.size(); n <<= 1, L++) ; A.resize(n); for (int k = 0; k < n; k++) A[ReverseBits(k)] = a[k]; } VC DFT(VC a, bool inverse) { BitReverseCopy(a); for (int s = 1; s <= L; s++) { int m = 1 << s; COMPLEX wm = exp(COMPLEX(0, 2.0 * M_PI / m)); if (inverse) wm = COMPLEX(1, 0) / wm; for (int k = 0; k < n; k += m) { COMPLEX w = 1; for (int j = 0; j < m/2; j++) { COMPLEX t = w * A[k + j + m/2]; COMPLEX u = A[k + j]; A[k + j] = u + t; A[k + j + m/2] = u - t; w = w * wm; } } } if (inverse) for (int i = 0; i < n; i++) A[i] /= n; return A; 9
10. sum_{i=0}^k a[i] b[k-i] VD Convolution(VD a, VD b) { int L = 1; while ((1 << L) < a.size()) L++; while ((1 << L) < b.size()) L++; int n = 1 << (L+1); VC aa, bb; for (size_t i = 0; i < n; i++) aa.push_back(i < a.size() ? COMPLEX(a[i], 0) : 0); for (size_t i = 0; i < n; i++) bb.push_back(i < b.size() ? COMPLEX(b[i], 0) : 0); VC AA = DFT(aa, VC BB = DFT(bb, VC CC; for (size_t i = VC cc = DFT(CC, false); false); 0; i < AA.size(); i++) CC.push_back(AA[i] * BB[i]); true); VD c; for (int i = 0; i < a.size() + b.size() - 1; i++) c.push_back(cc[i].real()); return c; } }; int main() { double a[] = {1, 3, 4, 5, 7}; double b[] = {2, 4, 6}; FFT fft; VD c = fft.Convolution(VD(a, a + 5), VD(b, b + 3)); // expected output: 2 10 26 44 58 58 42 for (int i = 0; i < c.size(); i++) cerr << c[i] << " "; cerr << endl; return 0; } 5) Simplex algorithm // // // // // // // // // // // // // // // // Two-phase simplex algorithm for solving linear programs of the form maximize subject to INPUT: A b c x - c^T x Ax <= b x >= 0 an m x n matrix an m-dimensional vector an n-dimensional vector a vector where the optimal solution will be stored OUTPUT: value of the optimal solution (infinity if unbounded above, nan if infeasible) To use this code, create an LPSolver object with A, b, and c as arguments. Then, call Solve(x).
include

include

include

include

include 10
11. double DOUBLE; vector VD; vector VVD; vector VI; const DOUBLE EPS = 1e-9; struct LPSolver { int m, n; VI B, N; VVD D; LPSolver(const VVD &A, const VD &b, const VD &c) : m(b.size()), n(c.size()), N(n+1), B(m), D(m+2, VD(n+2)) { for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) D[i][j] = A[i][j]; for (int i = 0; i < m; i++) { B[i] = n+i; D[i][n] = -1; D[i][n+1] = b[i]; } for (int j = 0; j < n; j++) { N[j] = j; D[m][j] = -c[j]; } N[n] = -1; D[m+1][n] = 1; } void Pivot(int r, int s) { for (int i = 0; i < m+2; i++) if (i != r) for (int j = 0; j < n+2; j++) if (j != s) D[i][j] -= D[r][j] * D[i][s] / D[r][s]; for (int j = 0; j < n+2; j++) if (j != s) D[r][j] /= D[r][s]; for (int i = 0; i < m+2; i++) if (i != r) D[i][s] /= -D[r][s]; D[r][s] = 1.0 / D[r][s]; swap(B[r], N[s]); } bool Simplex(int phase) { int x = phase == 1 ? m+1 : m; while (true) { int s = -1; for (int j = 0; j <= n; j++) { if (phase == 2 && N[j] == -1) continue; if (s == -1 || D[x][j] < D[x][s] || D[x][j] == D[x][s] && N[j] < N[s]) s = j; } if (D[x][s] >= -EPS) return true; int r = -1; for (int i = 0; i < m; i++) { if (D[i][s] <= 0) continue; if (r == -1 || D[i][n+1] / D[i][s] < D[r][n+1] / D[r][s] || D[i][n+1] / D[i][s] == D[r][n+1] / D[r][s] && B[i] < B[r]) r = i; } if (r == -1) return false; Pivot(r, s); } } DOUBLE Solve(VD &x) { int r = 0; for (int i = 1; i < m; i++) if (D[i][n+1] < D[r][n+1]) r = i; if (D[r][n+1] <= -EPS) { Pivot(r, n); if (!Simplex(1) || D[m+1][n+1] < -EPS) return numeric_limits::infinity(); for (int i = 0; i < m; i++) if (B[i] == -1) { int s = -1; for (int j = 0; j <= n; j++) 11
12. -1 || D[i][j] < D[i][s] || D[i][j] == D[i][s] && N[j] < N[s]) s = j; Pivot(i, s); } } if (!Simplex(2)) return numeric_limits::infinity(); x = VD(n); for (int i = 0; i < m; i++) if (B[i] < n) x[B[i]] = D[i][n+1]; return D[m][n+1]; } }; int main() { const int m = 4; const int n = 3; DOUBLE _A[m][n] = { { 6, -1, 0 }, { -1, -5, 0 }, { 1, 5, 1 }, { -1, -5, -1 } }; DOUBLE _b[m] = { 10, -4, 5, -5 }; DOUBLE _c[n] = { 1, -1, 0 }; VVD A(m); VD b(_b, _b + m); VD c(_c, _c + n); for (int i = 0; i < m; i++) A[i] = VD(_A[i], _A[i] + n); LPSolver solver(A, b, c); VD x; DOUBLE value = solver.Solve(x); cerr << "VALUE: "<< value << endl; cerr << "SOLUTION:"; for (size_t i = 0; i < x.size(); i++) cerr << " " << x[i]; cerr << endl; return 0; } 6) Prime lower than N // O(sqrt(x)) Exhaustive Primality Test
include

define EPS 1e-7 typedef long long LL; bool IsPrimeSlow (LL x) { if(x<=1) return false; if(x<=3) return true; if (!(x%2) || !(x%3)) return false; LL s=(LL)(sqrt((double)(x))+EPS); for(LL i=5;i<=s;i+=6) { if (!(x%i) || !(x%(i+2))) return false; } return true; } // Primes less than 1000: // 2 3 5 7 11 13 17 // 41 43 47 53 59 61 67 // 97 101 103 107 109 113 127 // 157 163 167 173 179 181 191 // 227 229 233 239 241 251 257 // 283 293 307 311 313 317 331 19 71 131 193 263 337 23 73 137 197 269 347 29 79 139 199 271 349 31 83 149 211 277 353 37 89 151 223 281 359 12
13. largest // The largest // The largest // The largest // The largest // The largest // The largest // The largest // The largest // The largest // The largest // The largest // The largest // The largest // The largest // The largest // The largest // The largest 379 449 523 607 677 761 853 937 383 457 541 613 683 769 857 941 389 461 547 617 691 773 859 947 prime prime prime prime prime prime prime prime prime prime prime prime prime prime prime prime prime prime smaller smaller smaller smaller smaller smaller smaller smaller smaller smaller smaller smaller smaller smaller smaller smaller smaller smaller 397 463 557 619 701 787 863 953 than than than than than than than than than than than than than than than than than than 401 467 563 631 709 797 877 967 409 479 569 641 719 809 881 971 419 487 571 643 727 811 883 977 421 491 577 647 733 821 887 983 431 499 587 653 739 823 907 991 433 503 593 659 743 827 911 997 10 is 7. 100 is 97. 1000 is 997. 10000 is 9973. 100000 is 99991. 1000000 is 999983. 10000000 is 9999991. 100000000 is 99999989. 1000000000 is 999999937. 10000000000 is 9999999967. 100000000000 is 99999999977. 1000000000000 is 999999999989. 10000000000000 is 9999999999971. 100000000000000 is 99999999999973. 1000000000000000 is 999999999999989. 10000000000000000 is 9999999999999937. 100000000000000000 is 99999999999999997. 1000000000000000000 is 999999999999999989. 7) The nth Fibonacci int64 fibonacci(int n) { int64 fib[2][2]= {{1,1},{1,0}},ret[2][2]= {{1,0},{0,1}},tmp[2][2]= {{0,0},{0,0}}; int i,j,k; while(n) { if(n&1) { memset(tmp,0,sizeof tmp); for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++) tmp[i][j]=(tmp[i][j]+ret[i][k]*fib[k][j]); for(i=0; i<2; i++) for(j=0; j<2; j++) ret[i][j]=tmp[i][j]; } memset(tmp,0,sizeof tmp); for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++) tmp[i][j]=(tmp[i][j]+fib[i][k]*fib[k][j]); for(i=0; i<2; i++) for(j=0; j<2; j++) fib[i][j]=tmp[i][j]; n/=2; } return (ret[0][1]); } 8) Read double with 100 character numbers
include

include using namespace std; int main() { double n,p; cout.setf(ios::fixed,ios::floatfield); 13
14.
15. TỔ HỢP 9) Dinic’s Algorithm // // // // // // // // // // // // // // // Adjacency list implementation of Dinic's blocking flow algorithm. This is very fast in practice, and only loses to push-relabel flow. Running time: O(|V|^2 |E|) INPUT: - graph, constructed using AddEdge() - source - sink OUTPUT: - maximum flow value - To obtain the actual flow values, look at all edges with capacity > 0 (zero capacity edges are residual edges).
include

include

include

include using namespace std; const int INF = 2000000000; struct Edge { int from, to, cap, flow, index; Edge(int from, int to, int cap, int flow, int index) : from(from), to(to), cap(cap), flow(flow), index(index) {} }; struct Dinic { int N; vector > G; vector dad; vector Q; Dinic(int N) : N(N), G(N), dad(N), Q(N) {} void AddEdge(int from, int to, int cap) { G[from].push_back(Edge(from, to, cap, 0, G[to].size())); if (from == to) G[from].back().index++; G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1)); } long long BlockingFlow(int s, int t) { fill(dad.begin(), dad.end(), (Edge *) NULL); dad[s] = &G[0][0] - 1; int head = 0, tail = 0; Q[tail++] = s; while (head < tail) { int x = Q[head++]; for (int i = 0; i < G[x].size(); i++) { Edge &e = G[x][i]; if (!dad[e.to] && e.cap - e.flow > 0) { dad[e.to] = &G[x][i]; Q[tail++] = e.to; } } } 15
16. 0; long long totflow = 0; for (int i = 0; i < G[t].size(); i++) { Edge *start = &G[G[t][i].to][G[t][i].index]; int amt = INF; for (Edge *e = start; amt && e != dad[s]; e = dad[e->from]) { if (!e) { amt = 0; break; } amt = min(amt, e->cap - e->flow); } if (amt == 0) continue; for (Edge *e = start; amt && e != dad[s]; e = dad[e->from]) { e->flow += amt; G[e->to][e->index].flow -= amt; } totflow += amt; } return totflow; } long long GetMaxFlow(int s, int t) { long long totflow = 0; while (long long flow = BlockingFlow(s, t)) totflow += flow; return totflow; } }; 10) Min cost max-flow // // // // // // // // // // // // // // // // // Implementation of min cost max flow algorithm using adjacency matrix (Edmonds and Karp 1972). This implementation keeps track of forward and reverse edges separately (so you can set cap[i][j] != cap[j][i]). For a regular max flow, set all edge costs to 0. Running time, O(|V|^2) cost per augmentation max flow: O(|V|^3) augmentations min cost max flow: O(|V|^4 * MAX_EDGE_COST) augmentations INPUT: - graph, constructed using AddEdge() - source - sink OUTPUT: - (maximum flow value, minimum cost value) - To obtain the actual flow, look at positive values only.
include

include

include using namespace std; typedef typedef typedef typedef typedef typedef typedef vector VI; vector VVI; long long L; vector VL; vector VVL; pair PII; vector VPII; const L INF = numeric_limits::max() / 4; struct MinCostMaxFlow { int N; 16
17. cost; VI found; VL dist, pi, width; VPII dad; MinCostMaxFlow(int N) : N(N), cap(N, VL(N)), flow(N, VL(N)), cost(N, VL(N)), found(N), dist(N), pi(N), width(N), dad(N) {} void AddEdge(int from, int to, L cap, L cost) { this->cap[from][to] = cap; this->cost[from][to] = cost; } void Relax(int s, int k, L cap, L cost, int dir) { L val = dist[s] + pi[s] - pi[k] + cost; if (cap && val < dist[k]) { dist[k] = val; dad[k] = make_pair(s, dir); width[k] = min(cap, width[s]); } } L Dijkstra(int s, int t) { fill(found.begin(), found.end(), false); fill(dist.begin(), dist.end(), INF); fill(width.begin(), width.end(), 0); dist[s] = 0; width[s] = INF; while (s != -1) { int best = -1; found[s] = true; for (int k = 0; k < N; k++) { if (found[k]) continue; Relax(s, k, cap[s][k] - flow[s][k], cost[s][k], 1); Relax(s, k, flow[k][s], -cost[k][s], -1); if (best == -1 || dist[k] < dist[best]) best = k; } s = best; } for (int k = 0; k < N; k++) pi[k] = min(pi[k] + dist[k], INF); return width[t]; } pair GetMaxFlow(int s, int t) { L totflow = 0, totcost = 0; while (L amt = Dijkstra(s, t)) { totflow += amt; for (int x = t; x != s; x = dad[x].first) { if (dad[x].second == 1) { flow[dad[x].first][x] += amt; totcost += amt * cost[dad[x].first][x]; } else { flow[x][dad[x].first] -= amt; totcost -= amt * cost[x][dad[x].first]; } } } return make_pair(totflow, totcost); } }; 17
18. Ford-Fulkerson // // // // // // // // // // // // // // // // // // // Adjacency list implementation of FIFO push relabel maximum flow with the gap relabeling heuristic. This implementation is significantly faster than straight Ford-Fulkerson. It solves random problems with 10000 vertices and 1000000 edges in a few seconds, though it is possible to construct test cases that achieve the worst-case. Running time: O(|V|^3) INPUT: - graph, constructed using AddEdge() - source - sink OUTPUT: - maximum flow value - To obtain the actual flow values, look at all edges with capacity > 0 (zero capacity edges are residual edges).
include

include

include

include using namespace std; typedef long long LL; struct Edge { int from, to, cap, flow, index; Edge(int from, int to, int cap, int flow, int index) : from(from), to(to), cap(cap), flow(flow), index(index) {} }; struct PushRelabel { int N; vector > G; vector excess; vector dist, active, count; queue Q; PushRelabel(int N) : N(N), G(N), excess(N), dist(N), active(N), count(2*N) {} void AddEdge(int from, int to, int cap) { G[from].push_back(Edge(from, to, cap, 0, G[to].size())); if (from == to) G[from].back().index++; G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1)); } void Enqueue(int v) { if (!active[v] && excess[v] > 0) { active[v] = true; Q.push(v); } } void Push(Edge &e) { int amt = int(min(excess[e.from], LL(e.cap - e.flow))); if (dist[e.from] <= dist[e.to] || amt == 0) return; e.flow += amt; G[e.to][e.index].flow -= amt; excess[e.to] += amt; excess[e.from] -= amt; Enqueue(e.to); } 18
19. { for (int v = 0; v < N; v++) { if (dist[v] < k) continue; count[dist[v]]; dist[v] = max(dist[v], N+1); count[dist[v]]++; Enqueue(v); } } void Relabel(int v) { count[dist[v]]; dist[v] = 2*N; for (int i = 0; i < G[v].size(); i++) if (G[v][i].cap - G[v][i].flow > 0) dist[v] = min(dist[v], dist[G[v][i].to] + 1); count[dist[v]]; Enqueue(v); } void Discharge(int v) { for (int i = 0; excess[v] > 0 && i < G[v].size(); i) Push(G[v][i]); if (excess[v] > 0) { if (count[dist[v]] == 1) Gap(dist[v]); else Relabel(v); } } LL GetMaxFlow(int s, int t) { count[0] = N-1; count[N] = 1; dist[s] = N; active[s] = active[t] = true; for (int i = 0; i < G[s].size(); i++) { excess[s] += G[s][i].cap; Push(G[s][i]); } while (!Q.empty()) { int v = Q.front(); Q.pop(); active[v] = false; Discharge(v); } LL totflow = 0; for (int i = 0; i < G[s].size(); i++) totflow += G[s][i].flow; return totflow; } }; 19
20. Matching /////////////////////////////////////////////////////////////////////////// // Min cost bipartite matching via shortest augmenting paths // // This is an O(n^3) implementation of a shortest augmenting path // algorithm for finding min cost perfect matchings in dense // graphs. In practice, it solves 1000x1000 problems in around 1 // second. // // cost[i][j] = cost for pairing left node i with right node j // Lmate[i] = index of right node that left node i pairs with // Rmate[j] = index of left node that right node j pairs with // // The values in cost[i][j] may be positive or negative. To perform // maximization, simply negate the cost[][] matrix. ///////////////////////////////////////////////////////////////////////////
include

include

include

include using namespace std; typedef vector VD; typedef vector VVD; typedef vector VI; double MinCostMatching(const VVD &cost, VI &Lmate, VI &Rmate) { int n = int(cost.size()); // construct dual feasible solution VD u(n); VD v(n); for (int i = 0; i < n; i++) { u[i] = cost[i][0]; for (int j = 1; j < n; j++) u[i] = min(u[i], cost[i][j]); } for (int j = 0; j < n; j++) { v[j] = cost[0][j] - u[0]; for (int i = 1; i < n; i++) v[j] = min(v[j], cost[i][j] - u[i]); } // construct primal solution satisfying complementary slackness Lmate = VI(n, -1); Rmate = VI(n, -1); int mated = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (Rmate[j] != -1) continue; if (fabs(cost[i][j] - u[i] - v[j]) < 1e-10) { Lmate[i] = j; Rmate[j] = i; mated++; break; } } } VD dist(n); VI dad(n); VI seen(n); // repeat until primal solution is feasible 20
21. n) { // find an unmatched left node int s = 0; while (Lmate[s] != -1) s++; // initialize Dijkstra fill(dad.begin(), dad.end(), -1); fill(seen.begin(), seen.end(), 0); for (int k = 0; k < n; k++) dist[k] = cost[s][k] - u[s] - v[k]; int j = 0; while (true) { // find closest j = -1; for (int k = 0; k < n; k++) { if (seen[k]) continue; if (j == -1 || dist[k] < dist[j]) j = k; } seen[j] = 1; // termination condition if (Rmate[j] == -1) break; // relax neighbors const int i = Rmate[j]; for (int k = 0; k < n; k++) { if (seen[k]) continue; const double new_dist = dist[j] + cost[i][k] - u[i] - v[k]; if (dist[k] > new_dist) { dist[k] = new_dist; dad[k] = j; } } } // update dual variables for (int k = 0; k < n; k++) { if (k == j || !seen[k]) continue; const int i = Rmate[k]; v[k] += dist[k] - dist[j]; u[i] -= dist[k] - dist[j]; } u[s] += dist[j]; // augment along path while (dad[j] >= 0) { const int d = dad[j]; Rmate[j] = Rmate[d]; Lmate[Rmate[j]] = j; j = d; } Rmate[j] = s; Lmate[s] = j; mated++; } double value = 0; for (int i = 0; i < n; i++) value += cost[i][Lmate[i]]; return value; 21
22. Matching // This code performs maximum bipartite matching. // // Running time: O(|E| |V|) -- often much faster in practice // // INPUT: w[i][j] = edge between row node i and column node j // OUTPUT: mr[i] = assignment for row node i, -1 if unassigned // mc[j] = assignment for column node j, -1 if unassigned // function returns number of matches made
include using namespace std; typedef vector VI; typedef vector VVI; bool FindMatch(int i, const VVI &w, VI &mr, VI &mc, VI &seen) { for (int j = 0; j < w[i].size(); j++) { if (w[i][j] && !seen[j]) { seen[j] = true; if (mc[j] < 0 || FindMatch(mc[j], w, mr, mc, seen)) { mr[i] = j; mc[j] = i; return true; } } } return false; } int BipartiteMatching(const VVI &w, VI &mr, VI &mc) { mr = VI(w.size(), -1); mc = VI(w[0].size(), -1); int ct = 0; for (int i = 0; i < w.size(); i++) { VI seen(w[0].size()); if (FindMatch(i, w, mr, mc, seen)) ct++; } return ct; } 14) Lát cắt trên đồ thị // // // // // // // // // // Adjacency matrix implementation of Stoer-Wagner min cut algorithm. Running time: O(|V|^3) INPUT: - graph, constructed using AddEdge() OUTPUT: - (min cut value, nodes in half of min cut)

include

include

include using namespace std; typedef vector VI; typedef vector VVI; 22
23. = 1000000000; pair GetMinCut(VVI &weights) { int N = weights.size(); VI used(N), cut, best_cut; int best_weight = -1; for (int phase = N-1; phase >= 0; phase--) { VI w = weights[0]; VI added = used; int prev, last = 0; for (int i = 0; i < phase; i++) { prev = last; last = -1; for (int j = 1; j < N; j++) if (!added[j] && (last == -1 || w[j] > w[last])) last = j; if (i == phase-1) { for (int j = 0; j < N; j++) weights[prev][j] += weights[last][j]; for (int j = 0; j < N; j++) weights[j][prev] = weights[prev][j]; used[last] = true; cut.push_back(last); if (best_weight == -1 || w[last] < best_weight) { best_cut = cut; best_weight = w[last]; } } else { for (int j = 0; j < N; j++) w[j] += weights[last][j]; added[last] = true; } } } return make_pair(best_weight, best_cut); } 15) Graph Cut Inference // // // // // // // // // // // // // // // // // // // // // // // // // Special-purpose {0,1} combinatorial optimization solver for problems of the following by a reduction to graph cuts: minimize x[1]...x[n] in {0,1} sum_i psi_i(x[i]) + sum_{i < j} phi_{ij}(x[i], x[j]) where psi_i : {0, 1} > R phi_{ij} : {0, 1} x {0, 1} > R such that phi_{ij}(0,0) + phi_{ij}(1,1) <= phi_{ij}(0,1) + phi_{ij}(1,0) (*) This can also be used to solve maximization problems where the direction of the inequality in (*) is reversed. INPUT: phi a matrix such that phi[i][j][u][v] = phi_{ij}(u, v) psi a matrix such that psi[i][u] = psi_i(u) x -- a vector where the optimal solution will be stored OUTPUT: value of the optimal solution To use this code, create a GraphCutInference object, and call the DoInference() method. To perform maximization instead of minimization, ensure that
define MAXIMIZATION is enabled.

include

include 23
24. VI; vector VVI; vector VVVI; vector VVVVI; const int INF = 1000000000; // comment out following line for minimization
define MAXIMIZATION struct GraphCutInference { int N; VVI cap, flow; VI reached; int Augment(int s, int t, int a) { reached[s] = 1; if (s == t) return a; for (int k = 0; k < N; k++) { if (reached[k]) continue; if (int aa = min(a, cap[s][k] - flow[s][k])) { if (int b = Augment(k, t, aa)) { flow[s][k] += b; flow[k][s] -= b; return b; } } } return 0; } int GetMaxFlow(int s, int t) { N = cap.size(); flow = VVI(N, VI(N)); reached = VI(N); int totflow = 0; while (int amt = Augment(s, t, INF)) { totflow += amt; fill(reached.begin(), reached.end(), 0); } return totflow; } int DoInference(const VVVVI &phi, const VVI &psi, VI &x) { int M = phi.size(); cap = VVI(M+2, VI(M+2)); VI b(M); int c = 0; for (int i = 0; i < M; i++) { b[i] += psi[i][1] - psi[i][0]; c += psi[i][0]; for (int j = 0; j < i; j++) b[i] += phi[i][j][1][1] - phi[i][j][0][1]; for (int j = i+1; j < M; j++) { cap[i][j] = phi[i][j][0][1] + phi[i][j][1][0] - phi[i][j][0][0] phi[i][j][1][1]; b[i] += phi[i][j][1][0] - phi[i][j][0][0]; c += phi[i][j][0][0]; } } 24
25. i = 0; i < M; i++) { for (int j = i+1; j < M; j++) cap[i][j] *= -1; b[i] *= -1; } c *= -1;
endif for (int i = 0; i < M; i++) { if (b[i] >= 0) { cap[M][i] = b[i]; } else { cap[i][M+1] = -b[i]; c += b[i]; } } int score = GetMaxFlow(M, M+1); fill(reached.begin(), reached.end(), 0); Augment(M, M+1, INF); x = VI(M); for (int i = 0; i < M; i++) x[i] = reached[i] ? 0 : 1; score += c;

ifdef MAXIMIZATION score *= -1;

endif return score; } }; int main() { // solver for "Cat vs. Dog" from NWERC 2008 int numcases; cin >> numcases; for (int caseno = 0; caseno < numcases; caseno++) { int c, d, v; cin >> c >> d >> v; VVVVI phi(c+d, VVVI(c+d, VVI(2, VI(2)))); VVI psi(c+d, VI(2)); for (int i = 0; i < v; i++) { char p, q; int u, v; cin >> p >> u >> q >> v; u--; v--; if (p == 'C') { phi[u][c+v][0][0]; phi[c+v][u][0][0]; } else { phi[v][c+u][1][1]; phi[c+u][v][1][1]; } } GraphCutInference graph; VI x; cout << graph.DoInference(phi, psi, x) << endl; } 25
26. flow using Ford-Fulkerson
include

define min(a, b) (((a)<(b))?(a):(b))

define INF 1000000000 //global variables int n; int cap[MAXN][MAXN]; bool v[MAXN]; int source, sink; //returns the capacity of the path. zero if there isn't one int augment(int x, int minedge) { if(x==sink) return minedge; v[x]=true; for(int i=0;i
include

include

include using namespace std; main() { freopen("G.inp","r",stdin); list G[1000]; int n; cin>>n; int tg; int v; for(int i=1;i<=n;i++) { 26
27. = 1; i<=n; i++) { for(list::iterator vii=G[i].begin();vii!=G[i].end();vii++) cout<<*vii<<" "; cout<
include

include

define MAXN 1001 using namespace std; struct Node { int x; int dinh; }; list Graph[MAXN]; int G[MAXN][MAXN]; int N; main() { freopen("BFS1.INP", "r", stdin); freopen("BFS_adj.OUT", "w", stdout); cin>>N; for(int i = 1; i<=N-1; i++) for(int j = i+1; j<=N; j++) { int x; cin>>x; if(x>=0) { Node d; d.x = x; d.dinh = j; Graph[i].push_front(d); } } for(int i = 1; i<=N; i++) { cout<<"Dinh thu "<::iterator itor = Graph[i].begin(); itor!=Graph[i].end(); it or++) 27
28. "<<(*itor).x<<" -> "; } cout<
29. Depth First Search
include

include

include

define NMAX 1000 using namespace std; int N, s, e; int A[NMAX][NMAX]; bool CX[NMAX]; vector vet; void print() { cout<<"Vet tim duoc la: "; for(vector::iterator itor=vet.begin(); itor!=vet.end(); itor++) cout<<*itor<<" "; cout<>N>>s>>e; for(int i=1 ; i <= N-1 ; i++) for(int j = i+1 ; j <= N; j++) { cin>>A[i][j]; A[j][i]=A[i][j]; } //In ra ma tran ke for(int i=1 ; i <= N-1 ; i++) { for(int j = i+1 ; j <= N; j++) { cout<
30. tien DFS(s, e); } Samples Input 717 110000 10010 1100 101 10 1 b) Breath First Search

include

include

include

include

define NMAX 1000 using namespace std; int N, s, e; int A[NMAX][NMAX]; bool CX[NMAX]; int Trace[NMAX], Length[NMAX]; queue que; void print() { cout<<"Duong di tim duoc la: "; int k = e; do { cout<
31. "w", stdout); cin>>N>>s>>e; for(int i=1 ; i <= N-1 ; i++) for(int j = i+1 ; j <= N; j++) { cin>>A[i][j]; A[j][i]=A[i][j]; } //In ra ma tran ke for(int i=1 ; i <= N ; i++) { for(int j = 1 ; j <= N; j++) { cout<
32. PATH a) Thuật toán FLOYD

include

include

include

define MAXN 1001 using namespace std; int A[MAXN][MAXN]; int Trace[MAXN][MAXN]; int N, M, K; vector vet; void print() { for(int i = vet.size()-1; i>=0; i--) cout<>N>>M>>K; cin>>N; for(int i = 1; i>x; if(x==-1) x=9999999; A[i][j] = A[j][i] = x; if(9999999!=x) { Trace[i][j]=i; Trace[j][i] = j; } } //Thuat toan Floyd for(int i = 1; i<=N; i++) { for(int j = 1; j<=N; j++) { for(int k = 1; k<=N; k++) { if(A[i][k]+A[k][j]
33. = A[i][k]+A[k][j]; Trace[i][j]=Trace[j][i]=k; } } } } cout<<"Duong di ngan nhat tu 1->7 = "<
include

include

define MAXN 1001

define MAXX 999999999 using namespace std; int A[MAXN][MAXN]; int MinPath[MAXN]; int From[MAXN]; bool Free[MAXN]; int M, N, S, E; void init() { freopen("DIJKSTRA.INP", "r", stdin); freopen("DIJKSTRA.OUT", "w", stdout); //Doc file input scanf("%d %d %d %d", &N, &M, &S, &E); for(int i = 1; i<=M; i++) { int u, v, p; scanf("%d %d %d", &u, &v, &p); A[u][v] = A[v][u] = p; } //Gan duong di ngan nhat = MAXX for(int i = 1; i<=N; i++) MinPath[i] = MAXX; MinPath[S] = 0; } void DIJKSTRA() { int g = S, minD; do { g=E; for(int i = 1; i<=N; i++) 33
34. && MinPath[g] > MinPath[i]) { g = i; } Free[g] = true; //Gan nhan cho dinh G co' dinh if(MinPath[g] == MAXX || g==E) break; for(int v = 1; v<=N; v++) { if(A[g][v] > 0 && !Free[v]) { if(A[g][v] + MinPath[g] < MinPath[v]) { MinPath[v] = A[g][v] + MinPath[g]; From[v] = g; } } } } while(true); } void TruyVet(int end) { int u = end; vector vet; while(u!=S) { vet.push_back(u); u = From[u]; } vet.push_back(S); printf("nVet tim duoc: "); for(int i = vet.size()-1; i>=0; i--) printf("%3d", vet[i]); printf("n"); } void print() { if(MinPath[E] == MAXX) printf("Khong co duong di!"); else printf("Duong di ngan nhat la: %d", MinPath[E]); } main() { init(); DIJKSTRA(); print(); TruyVet(E); } c) DIJKSTRA using Adjancy List // Implementation of Dijkstra's algorithm using adjacency lists // and priority queue for efficiency. // // Running time: O(|E| log |V|)

include

include using namespace std; const int INF = 2000000000; typedef pair PII; 34
35. s, t; scanf ("%d%d%d", &N, &s, &t); vector > edges(N); for (int i = 0; i < N; i++){ int M; scanf ("%d", &M); for (int j = 0; j < M; j++){ int vertex, dist; scanf ("%d%d", &vertex, &dist); edges[i].push_back (make_pair (dist, vertex)); // note order of arguments here } } // use priority queue in which top element has the "smallest" priority priority_queue, greater > Q; vector dist(N, INF), dad(N, -1); Q.push (make_pair (0, s)); dist[s] = 0; while (!Q.empty()){ PII p = Q.top(); if (p.second == t) break; Q.pop(); int here = p.second; for (vector::iterator it=edges[here].begin(); it!=edges[here].end(); it++){ if (dist[here] + it->first < dist[it->second]){ dist[it->second] = dist[here] + it->first; dad[it->second] = here; Q.push (make_pair (dist[it->second], it->second)); } } } printf ("%dn", dist[t]); if (dist[t] < INF) for(int i=t;i!=-1;i=dad[i]) printf ("%d%c", i, (i==s?'n':' ')); return 0; } 4) Strong connected Component
include struct edge{int e, nxt;}; int V, E; edge e[MAXE], er[MAXE]; int sp[MAXV], spr[MAXV]; int group_cnt, group_num[MAXV]; bool v[MAXV]; int stk[MAXV]; void fill_forward(int x) { int i; v[x]=true; for(i=sp[x];i;i=e[i].nxt) if(!v[e[i].e]) fill_forward(e[i].e); stk[++stk[0]]=x; } void fill_backward(int x) { int i; 35
36. add_edge(int v1, int v2) //add edge v1->v2 { e [E].e=v2; e [E].nxt=sp [v1]; sp [v1]=E; er[ E].e=v1; er[E].nxt=spr[v2]; spr[v2]=E; } void SCC() { int i; stk[0]=0; memset(v, false, sizeof(v)); for(i=1;i<=V;i) if(!v[i]) fill_forward(i); group_cnt=0; for(i=stk[0];i>=1;i--) if(v[stk[i]]){group_cnt++; fill_backward(stk[i]);} } 36
37. MATCHING a) Knuth-Morris-Pratt using System; namespace Knuth_Morris_Pratt { class Test { private char[] s; private char[] p; public void Nhap() { Console.Write("Nhap xau S:"); string stdin1 = Console.ReadLine(); s = new char[stdin1.Length]; s = stdin1.ToCharArray(); Console.Write("Nhap xau P:"); string stdin2 = Console.ReadLine(); p = new char[stdin2.Length]; p = stdin2.ToCharArray(); } private int[] compute_MP_map() // map[i]=| border(p[0..i-1]) | { int m = p.Length; // p is the input pattern int[] MP_map = new int[m + 1]; // lưu ý rằng ta phải tính map[0..m] // init MP_map[0] = -1; // cái này chắc ai cũng hiểu // bay gio di tinh map[1..m] int i = 0; int j = MP_map[i]; while (i < m) { while (j >= 0 && (p[i] != p[j])) j = MP_map[j]; j++; i++; MP_map[i] = j; } return MP_map; } private int[] compute_KMP_map() //thuật toán KMP cải tiến { int m = p.Length; int[] KMP_map = new int[m + 1]; int[] MP_map = compute_MP_map(); KMP_map[0] = -1; KMP_map[m] = MP_map[m]; for (int i = 1; i < m; i++) { int j = MP_map[i]; if (p[i] != p[j]) KMP_map[i] = j; else KMP_map[i] = MP_map[j]; } return KMP_map; } public void Morris_Pratt() { int[] map = compute_KMP_map(); int n = s.Length; int m = p.Length; int i = 0; string res = ""; for (int j = 0; j < n; j++) { while ((i >= 0) && (p[i] != s[j])) i = map[i]; i++; // Có 2 khả năng xảy ra: hoặc là đã đi hết chuỗi p (i=m-1) hoặc là i=-1 , lợi dụng cả 2 điều này if (i == m) { res += (j - m + 1).ToString() + " "; i = map[i]; 37
38. args) { Test object1 = new Test(); object1.Nhap(); object1.Morris_Pratt(); Console.ReadLine(); } } } C++ IMPLEMENT
include

include using namespace std; int m, n, i, j; int Next[100000]; string a; string b; void PREKMP() { i=0; j=-1; Next[0]=0; while (i-1 && b[i]!=b[j]) j=Next[j]; i++; j++; if(b[i]==b[j]) Next[i]=Next[j]; else Next[i]=j; } } void KMP() { i=0; j=0; while(j=0 && a[j]!=b[i]) i=Next[i]; i++; j++; if(i>m-1) { cout<
39. matching algorithm

include

include int *computePrefixFunction(char *P, int m) { int *pi=(int *)malloc(m*sizeof(int)); pi[0]=-1; int k=-1; for(int q=1;q=0 && P[k+1]!=P[q]) k=pi[k]; if(P[k+1]==P[q]) k++; pi[q]=k; } return pi; } void KMP(char *T, char *P) { int n=strlen(T), m=strlen(P); int *pi=computePrefixFunction(P, m); int q=-1; for(int i=0;i=0 && P[q+1]!=T[i]) q=pi[q]; if(P[q+1]==T[i]) q++; if(q==m) { //P occurs T[i-m+1..i]. Do whatever you want here q=pi[q]; } } } b) Boyer-More

include

include using namespace std; int m_badCharacterShift[256] ; int m_goodSuffixShift[1000001] ; int m_suffixes[1000001] ; string m_pattern; void BuildBadCharacterShift(string pattern) { for (int c = 0; c < 256; ++c) m_badCharacterShift[c] = pattern.size(); for (int i = 0; i < pattern.size() - 1; ++i) m_badCharacterShift[pattern[i]] = pattern.size() - i - 1; } void FindSuffixes(string pattern) { int f = 0, g; int patternLength = pattern.size(); m_suffixes[patternLength - 1] = patternLength; g = patternLength - 1; for (int i = patternLength - 2; i >= 0; --i) 39
40. g && m_suffixes[i + patternLength - 1 - f] < i - g) m_suffixes[i] = m_suffixes[i + patternLength - 1 - f]; else { if (i < g) g = i; f = i; while (g >= 0 && (pattern[g] == pattern[g + patternLength - 1 - f])) --g; m_suffixes[i] = f - g; } } } void BuildGoodSuffixShift(string pattern, int suff[]) { int patternLength = pattern.size(); for (int i = 0; i < patternLength; ++i) m_goodSuffixShift[i] = patternLength; int j = 0; for (int i = patternLength - 1; i >= -1; --i) if (i == -1 || suff[i] == i + 1) for (; j < patternLength - 1 - i; ++j) if (m_goodSuffixShift[j] == patternLength) m_goodSuffixShift[j] = patternLength - 1 - i; for (int i = 0; i <= patternLength - 2; ++i) m_goodSuffixShift[patternLength - 1 - suff[i]] = patternLength - 1 - i; } void setString(string pattern) { m_pattern = pattern; BuildBadCharacterShift(pattern); FindSuffixes(pattern); BuildGoodSuffixShift(pattern, m_suffixes); } int min2(int a, int b) { return ab?a:b; } void TurboBoyerMooreMatch(string text, int startingIndex) { int patternLength = m_pattern.size(); int textLength = text.size(); /* Searching */ int index = startingIndex; int overlap = 0; int shift = patternLength; while (index <= textLength - patternLength) { int unmatched = patternLength - 1; while (unmatched >= 0 && (m_pattern[unmatched] == text[unmatched + index])) { --unmatched; if (overlap != 0 && unmatched == patternLength - 1 - shift) unmatched -= overlap; 40
41. 0) { //return index; cout<>S>>P; setString(P); TurboBoyerMooreMatch(S, 0); //fclose(stdin); //freopen("CON", "r", stdin); //system("pause"); } 41
42. CÁC BÀI TOÁN QUY HOẠCH ĐỘNG ĐIỂN HÌNH Chúng ta đều biết rằng điều khó nhất để giải một bài toán quy hoạch động (QHĐ) là biết rằng nó là một bài toán QHĐ và tìm được công thức QHĐ của nó. Rất khó nếu ta mò mẫm từ đầu, nhưng nếu chúng ta đưa được bài toán cần giải về một bài toán QHĐ kinh điển thì sẽ dễ dàng hơn nhiều. Do đó, tìm hiểu mô hình, công thức và cách cài đặt những bài toán QHĐ kinh điển là một việc rất cần thiết. Trong chuyên đề này, tôi xin giới thiệu một số bài toán QHĐ kinh điển và những biến thể của chúng.Chủ yếu tập trung vào giới thiệu mô hình, công thức và một số gợi ý trong cài đặt chứ không đi chi tiết vào việc phát biểu bài toán, mô tả input/output, chứng minh công thức hay viết chương trình cụ thể. Mặc dù rất muốn minh hoạ cho các bài toán bằng các hình vẽ trực quan nhưng khuôn khổ có hạn nên tôi không thể đưa vào. Hơn nữa phần gợi ý cài đặt chỉ có gợi ý cho phần tính bảng phương án, phần lần vết cần có các cấu trúc dữ liệu và những kĩ thuật xử lí phức tạp xin dành lại cho các bạn. a) Dãy con đơn điệu dài nhất 1. Mô hình Cho dãy a1,a2,..an. Hãy tìm một dãy con tăng có nhiều phần tử nhất của dãy. Đặc trưng: i) Các phần tử trong dãy kết quả chỉ xuất hiện 1 lần. Vì vậy phương pháp làm là ta sẽ dùng vòng For duyệt qua các phần tử ai trong dãy, khác với các bài toán của mô hình 4(đặc trưng là bài toán đổi tiền), các phần tử trong dãy có thể được chọn nhiều lần nên ta thực hiện bằng phương pháp cho giá trị cần quy đổi tăng dần từng đơn vị. ii) Thứ tự của các phần tử được chọn phải được giữ nguyên so với dãy ban đầu. Đặc trưng này có thể mất đi trong một số bài toán khác tùy vào yêu cầu cụ thể. Chẳng hạn bài Tam giác bao nhau. 2. Công thức QHĐ Hàm mục tiêu : f = độ dài dãy con. Vì độ dài dãy con chỉ phụ thuộc vào 1 yếu tố là dãy ban đầu nên bảng phương án là bảng một chiều. Gọi L(i) là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ a1 đến ai và phần tử cuối cùng là ai. Nhận xét với cách làm này ta đã chia 1 bài toán lớn (dãy con của n số) thành các bài toán con cùng kiểu có kích thước nhỏ hơn (dãy con của dãy i số). Vấn đề là công thức truy hồi để phối hợp kết quả của các bài toán con. Ta có công thức QHĐ để tính L(i) như sau: • L(1) = 1. (Hiển nhiên) • L(i) = max(1, L(j)+1 với mọi phần tử j: 0
43. (L[i]
include

include

include using namespace std; typedef vector VI; typedef pair PII; typedef vector VPII;

define STRICTLY_INCREASNG VI LongestIncreasingSubsequence(VI v) { VPII best; VI dad(v.size(), -1); for (int i = 0; i < v.size(); i++) {

ifdef STRICTLY_INCREASNG PII item = make_pair(v[i], 0); VPII::iterator it = lower_bound(best.begin(), best.end(), item); item.second = i;

else PII item = make_pair(v[i], i); VPII::iterator it = upper_bound(best.begin(), best.end(), item);

endif if (it == best.end()) { dad[i] = (best.size() == 0 ? -1 : best.back().second); best.push_back(item); } else { dad[i] = dad[it->second]; *it = item; } } VI ret; for (int i = best.back().second; i >= 0; i = dad[i]) ret.push_back(v[i]); reverse(ret.begin(), ret.end()); return ret; } 4. Một số bài toán khác Bài toán dãy con đơn điệu tăng dài nhất có biến thể đơn giản nhất là bài toán dãy con đơn điệu giảm dài nhất, tuy nhiên chúng ta có thể coi chúng như là một. Sau đây là một số bài toán khác. 43
44. phòng họp( mất tính thứ tự so với dãy ban đầu) Có n cuộc họp, cuộc họp thứ i bắt đầu vào thời điểm ai và kết thúc ở thời điểm bi. Do chỉ có một phòng hội thảo nên 2 cuộc họp bất kì sẽ được cùng bố trí phục vụ nếu khoảng thời gian làm việc của chúng chỉ giao nhau tại đầu mút. Hãy bố trí phòng họp để phục vụ được nhiều cuộc họp nhất. Hướng dẫn: Sắp xếp các cuộc họp tăng dần theo thời điểm kết thúc (bi). Thế thì cuộc họp i sẽ bố trí được sau cuộc họp j nếu và chỉ nếu jai3<… hoặc ai1>ai2… • các chỉ số phải cách nhau ít nhất L: i2–i1≥L, i3–i2≥L…. • chênh lệch giữa 2 phần tử liên tiếp nhỏ hơn U: |ai1–ai2|≤U, |ai2–ai3|≤U… Hướng dẫn: Gọi L(i) là số phần tử của dãy con đổi dấu có phần tử cuối cùng là ai và phần tử cuối cùng lớn hơn phần tử đứng trước. Tương tự, P(i) là số phần tử của dãy con đổi dấu có phần tử cuối cùng là ai và phần tử cuối cùng nhỏ hơn phần tử đứng trước. Ta dễ dàng suy ra: • L(i) = max(1, P(j)+1): j≤i–L và ai–U≤aj
45. max(1, L(j)+1): j≤i–L và ai
46. W do If b[i]<=j then L[i,j]:=max(L(i-1,j-a[i]) + b[i], L[i-1,j]) else L[i,j]:=L[i-1,j]; 4. Một số bài toán khác a) Dãy con có tổng bằng S: Cho dãy a1,a2,..an. Tìm một dãy con của dãy đó có tổng bằng S. Hướng dẫn Đặt L[i,t)=1 nếu có thể tạo ra tổng t từ một dãy con của dãy gồm các phần tử a1,a2,..ai. Ngược lại thì L[i,t)=0. Nếu L[n,S)=1 thì đáp án của bài toán trên là “có”. Ta có thể tính L[i,t] theo công thức: L[i,t]=1 nếu L[i–1,t]=1 hoặc L[i–1,t–a[i]]=1. Cài đặt Nếu áp dụng luôn công thức trên thì ta cần dùng bảng phương án hai chiều. Ta có thể nhận xét rằng để tính dòng thứ i, ta chỉ cần dòng i–1. Bảng phương án khi đó chỉ cần 1 mảng 1 chiều L[0..S] và được tính như sau: L[t]:=0; L[0]:=1; for i := 1 to n do for t := S downto a[i] do if (L[t]=0) and (L[t–a[i]]=1) then L[t]:=1; Dễ thấy chi phí không gian của cách cài đặt trên là O(m), chi phí thời gian là O(nm), với m là tổng của n số. Hãy tự kiểm tra xem tại sao vòng for thứ 2 lại là for downto chứ không phải là for to. b) Chia kẹo Cho n gói kẹo, gói thứ i có ai viên. Hãy chia các gói thành 2 phần sao cho chênh lệch giữa 2 phần là ít nhất. Hướng dẫn: Gọi T là tổng số kẹo của n gói. Chúng ta cần tìm số S lớn nhất thoả mãn: • S≤T/2. • Có một dãy con của dãy a có tổng bằng S. Khi đó sẽ có cách chia với chênh lệch 2 phần là T–2S là nhỏ nhất và dãy con có tổng bằng S ở trên gồm các phần tử là các gói kẹo thuộc phần thứ nhất. Phần thứ hai là các gói kẹo còn lại. c) Market (Olympic Balkan 2000) Người đánh cá Clement bắt được n con cá, khối lượng mỗi con là ai, đem bán ngoài chợ. Ở chợ cá, người ta không mua cá theo từng con mà mua theo một lượng nào đó. Chẳng hạn 3 kg, 5kg… Ví dụ: có 3 con cá, khối lượng lần lượt là: 3, 2, 4. Mua lượng 6 kg sẽ phải lấy con cá thứ 2 và và thứ 3. Mua lượng 3 kg thì lấy con thứ nhất. Không thể mua lượng 8 kg. Nếu bạn là người đầu tiên mua cá, có bao nhiêu lượng bạn có thể chọn? Hướng dẫn: Thực chất bài toán là tìm các số S mà có một dãy con của dãy a có tổng bằng S. Ta có thể dùng phương pháp đánh dấu của bài chia kẹo ở trên rồi đếm các giá trị t mà L[t]=1. d) Điền dấu Cho n số tự nhiên a1,a2, ...,an. Ban đầu các số được đặt liên tiếp theo đúng thứ tự cách nhau bởi dấu "?": a1?a2?...?an. Cho trước số nguyên S, có cách nào thay các dấu "?" bằng dấu + hay dấu − để được một biểu thức số học cho giá trị là S không? Hướng dẫn: Đặt L(i,t)=1 nếu có thể điền dấu vào i số đầu tiên và cho kết quả bằng t. Ta có công 46
47. tính L: • L(1,a[1]) =1. • L(i,t)=1 nếu L(i–1,t+a[i])=1 hoặc L(i–1,t–a[i])=1. Nếu L(n,S)=1 thì câu trả lời của bài toán là có. Khi cài đặt, có thể dùng một mảng 2 chiều (lưu toàn bộ bảng phương án) hoặc 2 mảng một chiều (để lưu dòng i và dòng i–1). Chú ý là chỉ số theo t của các mảng phải có cả phần âm (tức là từ –T đến T, với T là tổng của n số), vì trong bài này chúng ta dùng cả dấu – nên có thể tạo ra các tổng âm. Bài này có một biến thể là đặt dấu sao cho kết quả là một số chia hết cho k. Ta có thuật giải tương tự bài toán trên bằng cách thay các phép cộng, trừ bằng các phép cộng và trừ theo môđun k và dùng mảng đánh dấu với các giá trị từ 0 đến k–1 (là các số dư có thể có khi chia cho k). Đáp số của bài toán là L(n,0). e) Expression (ACM 10690) Cho n số nguyên. Hãy chia chúng thành 2 nhóm sao cho tích của tổng 2 nhóm là lớn nhất. Hướng dẫn: Gọi T là tổng n số nguyên đó. Giả sử ta chia dãy thành 2 nhóm, gọi S là tổng của một nhóm, tổng nhóm còn lại là T–S và tích của tổng 2 nhóm là S*(T–S). Bằng phương pháp đánh dấu ta xác định được mọi số S là tổng của một nhóm (như bài Market) và tìm số S sao cho S*(T–S) đạt max. d) Biến đổi xâu: 1. Mô hình Cho 2 xâu X,F. Xâu nguồn có n kí tự X1X2...Xn , xâu đích có m kí tự F1F2...Fm .Có 3 phép biến đổi : • Chèn 1 kí tự vào sau kí tự thứ i :I i C • Thay thế kí tự ở vị trí thứ i bằng kí tự C : R i C. • Xoá kí tự ở vị trí thứ i. D i Hãy tìm số ít nhất các phép biến đổi để biến xâu X thành xâu F. Hướng dẫn: Hàm mục tiêu : f: số phép biến đổi. Dễ thấy số phép biến đổi phụ thuộc vào vị trí i đang xét của xâu X và vị trí j đang xét cuả xâu F. Do vậy để cài đặt cho bang phương án ta sẽ dùng mảng 2 chiều Gọi L(i,j) là số phép biến đổi ít nhất để biến xâu X(i) gồm i kí tự phần đầu của X (X(i)= X[1..i]) thành xâu F(j) gồm j kí tự phần đầu của F(F(j) =F[1..j]). Dễ thấy F(0,j)=j và F(i,0)=i. Có 2 trường hợp xảy ra: Nếu X[i]=F[j] : X1X2...Xi-1 Xi F1F2...Fj-1 Xi thì ta chỉ phải biến đổi xâu X(i-1) thành xâu Y(j-1). Do đó F(i,j)=F(i-1,j-1). Ngược lại, ta có 3 cách biến đổi: Xoá kí tự X[i]: X1X2...Xi-1 Xi F1F2...Fj-1 Fj Xâu X(i-1) thành F(j). Khi đó F(i,j)=F(i-1,j)+1.(Cộng 1 là do ta đã dùng 1 phép xóa) Thay thế X[i] bởi F[j] : X1X2...Xi-1 Fj F1F2...Fj-1 Fj 47
48. F(j-1). Khi đó F(i,j)=F(i-1,j-1)+1. Chèn F[j] vào X(i): X1X2...Xi-1 Xi Fj F1F2...Fj-1 Fj Xâu X(i) thành Y(j-1). Khi đó F(i,j)=F(i,j-1)+1. Tổng kết lại, ta có công thức QHĐ: • F(0,j)=j • F(i,0)=i • F(i,j) =F(i−1,j−1) nếu X[i] = Y[j]. • F(i,j) = min(F(i−1,j),F(i,j−1),F(i−1,j−1))+1 nếu X[i]≠Y[j]. Bài này ta có thể tiết kiệm biến hơn bằng cách dùng 2 mảng 1 chiều tính lẫn nhau và một mảng đánh dấu 2 chiều để truy vết. 4. Một số bài toán khác a) Xâu con chung dài nhất Cho 2 xâu X,Y. Hãy tìm xâu con của X và của Y có độ dài lớn nhất. Công thức QHĐ Gọi L(i,j) là độ dài xâu con chung dài nhất của xâu X(i) gồm i kí tự phần đầu của X (X(i)= X[1..i]) và xâu Y(j) gồm j kí tự phần đầu của Y (Y(j) =Y[1..j]). Ta có công thức quy hoạch động như sau: • L(0,j)=L(i,0)=0. • L(i,j) = L(i−1,j−1)+1 nếu X[i] = Y[j]. • L(i,j) = max(L(i−1,j), L(i,j−1)) nếu X[i]≠Y[j]. Cài đặt Bảng phương án là một mảng 2 chiều L[0..m,0..n] để lưu các giá trị của hàm QHĐ L(i,j). Đoạn chương trình cài đặt công thức QHĐ trên như sau: for i:=0 to m do L[i,0]:=0; for j:=0 to n do L[0,j]:=0; for i:=1 to m do for j:=1 to n do if X[i]=Y[j] then L[i,j]:=L[i–1,j–1]+1 else L[i,j]:=max(L[i–1,j],L[i,j–1]]); Như vậy chi phí không gian của bài toán là O(n2), chi phí thời gian là O(n2). Có một phương pháp cài đặt tốt hơn, chỉ với chi phí không gian O(n) dựa trên nhận xét sau: để tính ô L[i,j] của bảng phương án, ta chỉ cần 3 ô L[i–1,j–1],L[i–1,j] và L[i,j–1]. Tức là để tính dòng L[i] thì chỉ cần dòng L[i–1]. Do đó ta chỉ cần 2 mảng 1 chiều để lưu dòng vừa tính (P) và dòng đang tính (L) mà thôi. Cách cài đặt mới như sau: for j:=0 to n do P[j]:=0; for i:=1 to m do begin L[0] := 0; for j:=1 to n do if X[i]=Y[j] then L[i,j]:=P[j–1]+1 else L[i,j]:=max(P[j], L[j–1]); P := L; end; c) Bắc cầu Hai nước Anpha và Beta nằm ở hai bên bờ sông Omega, Anpha nằm ở bờ bắc và có M thành phố được đánh số từ 1 đến m, Beta nằm ở bờ nam và có N thành phố được đánh số từ 1 đến n (theo vị trí 48
49. tây). Mỗi thành phố của nước này thường có quan hệ kết nghĩa với một số thành phố của nước kia. Để tăng cường tình hữu nghị, hai nước muốn xây các cây cầu bắc qua sông, mỗi cây cầu sẽ là nhịp cầu nối 2 thành phố kết nghĩa. Với yêu cầu là các cây cầu không được cắt nhau và mỗi thành phố chỉ là đầu cầu cho nhiều nhất là một cây cầu, hãy chỉ ra cách bắc cầu được nhiều cầu nhất. Hướng dẫn: Gọi các thành phố của Anpha lần lượt là a1,a2,…am; các thành phố của Beta là b1,b2,...bn. Nếu thành phố ai và bj kết nghĩa với nhau thì coi ai “bằng” bj. Để các cây cầu không cắt nhau, nếu ta đã chọn cặp thành phố (ai,bj) để xây cầu thì cặp tiếp theo phải là cặp (au,bv) sao cho u>i và v>j. Như vậy các cặp thành phố được chọn xây cầu có thể coi là một dãy con chung của hai dãy a và b. Bài toán của chúng ta trở thành bài toán tìm dãy con chung dài nhất, ở đây hai phần tử “bằng” nhau nếu chúng có quan hệ kết nghĩa. d) Palindrom (IOI 2000) Một xâu gọi là xâu đối xứng (palindrom) nếu xâu đó đọc từ trái sang phải hay từ phải sang trái đều như nhau. Cho một xâu S, hãy tìm số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng. Hướng dẫn: Bài toán này có một công thức QHĐ như sau: Gọi L(i,j) là số kí tự ít nhất cần thêm vào xâu con S[i..j] của S để xâu đó trở thành đối xứng. Đáp số của bài toán sẽ là L(1,n) với n là số kí tự của S. Ta có công thức sau để tính L(i,j): • L(i,i)=0. • L(i,j)=L(i+1,j–1) nếu S[i]=S[j] • L(i,j)=max(L(i+1,j), L(i,j–1)) nếu S[i]≠S[j] Bạn đọc dễ dàng có thể kiểm chứng công thức đó. Ta có thể cài đặt trực tiếp công thức đó bằng phương pháp đệ quy có nhớ. Tuy nhiên khi đó chi phí không gian là O(n2). Có một phương pháp cài đặt tiết kiệm hơn (bạn đọc có thể tham khảo ở bài báo trên của thầy Trần Đỗ Hùng), tuy nhiên phương pháp đó khá phức tạp. Ta có thuật toán đơn giản hơn như sau: Gọi P là xâu đảo của S và T là xâu con chung dài nhất của S và P. Khi đó các kí tự của S không thuộc T cũng là các kí tự cần thêm vào để S trở thành đối xứng. Đáp số của bài toán sẽ là n–k, với k là độ dài của T. Ví dụ: S=edbabcd, xâu đảo của S là P=dcbabde. Xâu con chung dài nhất của S và P là T=dbabd. Như vậy cần thêm 2 kí tự là e và c vào để S trở thành xâu đối xứng. e) Vali (A) 1. Mô hình Cho n vật, vật i nặng ai và có giá trị bi. Hãy chọn ra một số vật để cho vào balô sao cho tổng khối lượng không vượt quá W và tổng giá trị là lớn nhất. Chú ý rằng mỗi vật có thể được chọn nhiều lần. 2. Công thức Gọi L(i,j) là tổng giá trị lớn nhất khi được chọn i vật từ 1 đến i cho vào balô với tổng khối lượng không vượt quá j. L(n,W) sẽ là đáp số của bài toán (là giá trị lớn nhất có được nếu chọn n vật và tổng khối lượng không vượt quá W). Công thức tính L(i,t) như sau: 49
50. L(i,j)=L(i,j) nếu t0. 50
51. ti+1 thì ta thấy có thể tính Ai.Ai+1....Aj bằng cách chọn một vị trí k nào đó để đặt ngoặc theo trình tự: Ai.Ai+1....Aj = (Ai..Ak).(Ak+1..Aj) Ma trận kết quả của phép nhân (Ai..Ak) có kích thước di–1×dk, ma trận kết quả của phép nhân (Ak+1..Aj) có kích thước dk×dj. Với cách đặt đó ta sẽ mất F(i,k) phép nhân để có kết quả trong dấu ngoặc thứ nhất, mất thêm F(k+1,j) phép nhân để có kết quả trong dấu ngoặc thứ hai, và cuối cùng mất di–1.dk.dj để nhân 2 ma trận kết quả đó. Từ đó tổng số phép nhân của cách đặt đó là: F(i,k)+F(k+1,j)+di–1.dk.dj. Ta chọn vị trí k cho số phép nhân ít nhất. 3. Cài đặt Bảng phương án là một mảng 2 chiều F để lưu F(i,j). Chú ý khi cài đặt là để tính được F(i,j), ta phải tính F(i,k) và F(k+1,j) trước. Phương pháp đơn giản để làm điều đó là phương pháp đệ quy có nhớ. Tuy nhiên dựa vào nhận xét là trong công thức QHĐ: j–i lớn hơn k–i và j–k, ta có thể tính theo trình tự khác: tính các phần tử F(i,j) với j–i từ nhỏ đến lớn (không phải là tính các giá trị F(i,j) với i,j từ nhỏ đến lớn như vẫn làm). Với cách đó, khi tính đến F(i,j) thì ta đã có F(i,k) và F(k+1,j). Đoạn chương trình tính bảng phương án như sau: for i:=1 to n do F[i,i]:=0; for i:=1 to n–1 do 51
52. m:=2 to n–1 do begin for i:=1 to n–m do begin j:=i+m; F[i,j]:=oo; for k:=i+1 to j–1 do F[i,j]:=min(F[i,j], F[i,k]+F[k+1,j]+d[i–1]*d[k]*d[j]); end; end; Với cách cài đặt trên,chi phí không gian là O(n2), chi phí thời gian là O(n3) (đây là bài toán có chi phí lớn nhất trong tất cả các bài toán QHĐ thường gặp). 4. Một số bài toán khác a) Chia đa giác Cho một đa giác lồi N đỉnh. Bằng các đường chéo không cắt nhau, ta có thể chia đa giác thành N–2 tam giác. Hãy xác định cách chia có tổng các đường chéo ngắn nhất. Hướng dẫn: Để đơn giản ta coi mọi đoạn thẳng nối 2 đỉnh đều là “đường chéo” (nếu nối 2 đỉnh trùng nhau hoặc 2 đỉnh liên tiếp thì có độ dài bằng 0). Gọi F(i,j) là tổng độ dài các đường chéo khi chia đa giác gồm các đỉnh từ i đến j thành các tam giác. Nếu ji+1 thì có thể tính biểu thức ai•ai+1•…•aj bằng cách chia thành 2 nhóm: (ai•ai+1•…•ak)•(ak+1•…•aj), Khi đó F(i,j)=F(i,k)•F(k+1,j). Tóm lại, công thức QHĐ là: • F(i,i)=ai • F(i,i+1)=ai•ai+1 • F(i,j)=max(F(i,k)•F(k+1,j) với k=i+1,i+2,..j–1). (Chú là là các hạng tử của dãy đều không âm và các phép toán là + hoặc × nên F(i,k) và F(k+1,j) đạt max thì F(i,k)•F(k+1,j) cũng đạt max). g) Ghép cặp 1.Mô hình Có n lọ hoa sắp thẳng hàng và k bó hoa được đánh số thứ tự từ nhỏ đến lớn. Cần cằm k bó hoa trên vào n lọ sao cho hoa có số thứ tự nhỏ phải đứng trước hoa có số thứ tự lớn. Giá trị thẩm mỹ tương ứng khi cắm hoa i vào lọ thứ j là v(i,j) Hãy tìm 1 cách cắm sao cho tổng giá trị thẫm mỹ là lớn nhất. Chú ý rằng mỗi bó hoa chỉ được cắm vào 1 lọ và mỗi lọ cũng chỉ cắm được 1 bó hoa. (IOI – 1999) 2. Công thức : 52
53. bài toán nêu trên là một bài toán ghép cặp có yêu cầu về thứ tự nên ta có thể giải quyết bằng phương pháp QHĐ. Hàm mục tiêu : f: tổng giá trị thẩm mỹ của cách cắm. Giá trị thẩm mỹ phụ thuộc vào các hoa và các lọ đang được xét nên ta sẽ dùng mảng 2 chiều để lưu bảng phương án. L(i,j): tổng giá trị thẩm mỹ lớn nhất khi xét đến hoa i và lọ j. Khi tính L(i,j) hoa đang xét sẽ là hoa i và lọ j. • Nếu i = j. Chỉ có một cách cắm L(i,i):= v[1,1]+v[2,2]+...v[i,i] • Nếu i>j . Không có cách cắm hợp lý • Nếu i
54. kề cạnh. IQ của người chơi sẽ tỉ lệ thuận với số điểm nhận được. Sherry tham gia trò chơi và đạt kết quả khá tốt.Và bây giờ Sherry muốn biết tổng điểm lớn nhất nhận được trong trò chơi này là bao nhiêu. Bạn hãy giúp sherry nhé !!! Input Dòng 1 là số nguyên N ( 1 <= N <= 10000 ) 8 dòng tiếp theo: Mỗi dòng gồm n số nguyên. Số nguyên ở hàng i, cột j là Aij ( |Aij| <= 108 ) Output Gồm 1 dòng duy nhất là số điểm lớn nhất tìm được Example Input: 2 -22 2 -33 45 56 -60 -8 -38 79 66 -10 -23 99 46 1 -55 Output: 279 Giải thích: Chọn các ô (3,1) (5,1) (7,1) (2,2) Lời giải: Xét bảng 4*N, gọi F[i,j] là giá trị tối ưu khi xét đến cột i và j là số có 4 bit để miêu tả trạng thái của cột i(bit thứ k của số j =1 nếu như chọn ô k). F[i,j]=max (F[i-1,j'] + sum(i,j)) trong đó j' là cấu hình của cột thứ i-1 và j' và j thõa mãn với nhau, sum(i,x) là tổng của các số trong cột i tương đương với số j 3) MỘT SỐ BÀI TOÁN QUY HOẠCH ĐỘNG BỔ XUNG Cho dãy số gồm n số nguyên a0, a1, …, an-1. Giá trị tối ưu trên dãy số được tính bằng hàm f() như sau: f(i, j, k, z, l)=ai + 2*aj + 3*ak + 4*az + 5*al với 0 ≤ i < j < k < z < l < n
include

include

include using namespace std; int n; int hs[6]={0,1,2,3,4,5}; int a[10002]; int f[6][10002]; main(){ int i,sotest; //freopen("gttoiuu.inp","r",stdin); //freopen("timdaymaxout.txt","w",stdout); cin>>sotest; for(i=0;i>n; for(int i=1;i<=n;i++) cin>>a[i]; //thiet lap co so quy hoach dong for(int i=0;i<=n;i++) { f[0][i]=0; 54
55. dong for(int i=1;i<6;i++) { f[i][i]=f[i-1][i-1]+a[i]*hs[i]; for(int j=i+1;j<=n-5+i;j++) { f[i][j]=f[i][j-1]; if(f[i-1][j-1] + a[j]*hs[i]>f[i][j]) f[i][j]=f[i-1][j-1] + a[j]*hs[i]; } } cout<0;j--) if(f[i][j]!=f[i][j-1]){ cout<
56. Hull // // // // // // // // // Compute the 2D convex hull of a set of points using the monotone chain algorithm. Eliminate redundant points from the hull if REMOVE_REDUNDANT is
defined. Running time: O(n log n) INPUT: OUTPUT:

include

include

include

include

include a vector of input points, unordered. a vector of points in the convex hull, counterclockwise, starting with bottommost/leftmost point using namespace std;

define REMOVE_REDUNDANT typedef double T; const T EPS = 1e-7; struct PT { T x, y; PT() {} PT(T x, T y) : x(x), y(y) {} bool operator<(const PT &rhs) const { return make_pair(y,x) < make_pair(rhs.y,rhs.x); } bool operator==(const PT &rhs) const { return make_pair(y,x) == make_pair(rhs.y,rhs.x); } }; T cross(PT p, PT q) { return p.x*q.y-p.y*q.x; } T area2(PT a, PT b, PT c) { return cross(a,b) + cross(b,c) + cross(c,a); }

ifdef REMOVE_REDUNDANT bool between(const PT &a, const PT &b, const PT &c) { return (fabs(area2(a,b,c)) < EPS && (a.x-b.x)*(c.x-b.x) <= 0 && (a.y-b.y)*(c.yb.y) <= 0); }

endif void ConvexHull(vector &pts) { sort(pts.begin(), pts.end()); pts.erase(unique(pts.begin(), pts.end()), pts.end()); vector up, dn; for (int i = 0; i < pts.size(); i++) { while (up.size() > 1 && area2(up[up.size()-2], up.back(), pts[i]) >= 0) up.pop_back(); while (dn.size() > 1 && area2(dn[dn.size()-2], dn.back(), pts[i]) <= 0) dn.pop_back(); up.push_back(pts[i]); dn.push_back(pts[i]); } pts = dn; for (int i = (int) up.size() - 2; i >= 1; i--) pts.push_back(up[i]);

ifdef REMOVE_REDUNDANT if (pts.size() <= 2) return; dn.clear(); dn.push_back(pts[0]); 56
57. = 2; i < pts.size(); i++) { if (between(dn[dn.size()-2], dn[dn.size()-1], pts[i])) dn.pop_back(); dn.push_back(pts[i]); } if (dn.size() >= 3 && between(dn.back(), dn[0], dn[1])) { dn[0] = dn.back(); dn.pop_back(); } pts = dn;
endif } 2) Geometry Computation // C++ routines for computational geometry.

include

include

include

include using namespace std; double INF = 1e100; double EPS = 1e-12; struct PT { double x, y; PT() {} PT(double x, double y) : x(x), y(y) {} PT(const PT &p) : x(p.x), y(p.y) {} PT operator + (const PT &p) const { return PT operator - (const PT &p) const { return PT operator * (double c) const { return PT operator / (double c) const { return }; PT(x+p.x, PT(x-p.x, PT(x*c, PT(x/c, y+p.y); y-p.y); y*c ); y/c ); } } } } double dot(PT p, PT q) { return p.x*q.x+p.y*q.y; } double dist2(PT p, PT q) { return dot(p-q,p-q); } double cross(PT p, PT q) { return p.x*q.y-p.y*q.x; } ostream &operator<<(ostream &os, const PT &p) { os << "(" << p.x << "," << p.y << ")"; } // PT PT PT rotate a point CCW or CW around the origin RotateCCW90(PT p) { return PT(-p.y,p.x); } RotateCW90(PT p) { return PT(p.y,-p.x); } RotateCCW(PT p, double t) { return PT(p.x*cos(t)-p.y*sin(t), p.x*sin(t)+p.y*cos(t)); } // project point c onto line through a and b // assuming a != b PT ProjectPointLine(PT a, PT b, PT c) { return a + (b-a)*dot(c-a, b-a)/dot(b-a, b-a); } // project point c onto line segment through a and b PT ProjectPointSegment(PT a, PT b, PT c) { double r = dot(b-a,b-a); if (fabs(r) < EPS) return a; r = dot(c-a, b-a)/r; if (r < 0) return a; if (r > 1) return b; return a + (b-a)*r; 57

Giải bài tập toán 12 nâng cao hình họcb ai3

include

include

include

include

include

include

include 7

include

include

include

include

include

include

include 10

include

include

include using namespace std; int main() { double n,p; cout.setf(ios::fixed,ios::floatfield); 13

include

include

include

include

include

include using namespace std; typedef typedef typedef typedef typedef typedef typedef vector VI; vector VVI; long long L; vector VL; vector VVL; pair PII; vector VPII; const L INF = numeric_limits::max() / 4; struct MinCostMaxFlow { int N; 16

include

include

include

include

include

include

include

include

include using namespace std; typedef vector VI; typedef vector VVI; 22

define MAXIMIZATION is enabled.

include

include 23

endif for (int i = 0; i < M; i++) { if (b[i] >= 0) { cap[M][i] = b[i]; } else { cap[i][M+1] = -b[i]; c += b[i]; } } int score = GetMaxFlow(M, M+1); fill(reached.begin(), reached.end(), 0); Augment(M, M+1, INF); x = VI(M); for (int i = 0; i < M; i++) x[i] = reached[i] ? 0 : 1; score += c;

ifdef MAXIMIZATION score *= -1;

include

define min(a, b) (((a)<(b))?(a):(b))

include

include

include using namespace std; main() { freopen("G.inp","r",stdin); list G[1000]; int n; cin>>n; int tg; int v; for(int i=1;i<=n;i++) { 26

include

include

include

include

include

include

include

include

include

include

include

include

include

include

define MAXN 1001

include

include using namespace std; const int INF = 2000000000; typedef pair PII; 34

include

include

include

include

include

include using namespace std; typedef vector VI; typedef pair PII; typedef vector VPII;

define STRICTLY_INCREASNG VI LongestIncreasingSubsequence(VI v) { VPII best; VI dad(v.size(), -1); for (int i = 0; i < v.size(); i++) {

ifdef STRICTLY_INCREASNG PII item = make_pair(v[i], 0); VPII::iterator it = lower_bound(best.begin(), best.end(), item); item.second = i;

else PII item = make_pair(v[i], i); VPII::iterator it = upper_bound(best.begin(), best.end(), item);

include

include

defined. Running time: O(n log n) INPUT: OUTPUT:

include

include

include

include

include a vector of input points, unordered. a vector of points in the convex hull, counterclockwise, starting with bottommost/leftmost point using namespace std;

ifdef REMOVE_REDUNDANT bool between(const PT &a, const PT &b, const PT &c) { return (fabs(area2(a,b,c)) < EPS && (a.x-b.x)*(c.x-b.x) <= 0 && (a.y-b.y)*(c.yb.y) <= 0); }

ifdef REMOVE_REDUNDANT if (pts.size() <= 2) return; dn.clear(); dn.push_back(pts[0]); 56

endif } 2) Geometry Computation // C++ routines for computational geometry.

ifdef REMOVE_REDUNDANT bool between(const PT &a, const PT &b, const PT &c) { return (fabs(area2(a,b,c)) < EPS && (a.x-b.x)(c.x-b.x) <= 0 && (a.y-b.y)(c.yb.y) <= 0); }