Artifact 908cbaac8fbb72e4a82b2b44be0686c9f8d2abfe:
0000: 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .//-------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0040: 0a 2f 2f 20 4c 69 6e 65 61 72 20 45 71 75 61 74 .// Linear Equat
0050: 69 6f 6e 20 53 6f 6c 76 65 72 0a 2f 2f 20 20 20 ion Solver.//
0060: 4f 28 6e 5e 33 29 0a 2f 2f 0a 2f 2f 20 56 65 72 O(n^3).//.// Ver
0070: 69 66 69 65 64 20 62 79 0a 2f 2f 20 20 20 2d 20 ified by.// -
0080: 53 52 4d 20 33 39 38 20 44 69 76 31 20 4c 56 33 SRM 398 Div1 LV3
0090: 0a 2f 2f 20 20 20 2d 20 41 4f 4a 20 30 30 30 34 .// - AOJ 0004
00a0: 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .//-------------
00b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00e0: 0a 0a 76 65 63 74 6f 72 3c 64 6f 75 62 6c 65 3e ..vector<double>
00f0: 20 73 6f 6c 76 65 5f 6c 69 6e 65 61 72 5f 65 71 solve_linear_eq
0100: 28 20 69 6e 74 20 6e 2c 20 76 65 63 74 6f 72 3c ( int n, vector<
0110: 20 76 65 63 74 6f 72 3c 64 6f 75 62 6c 65 3e 20 vector<double>
0120: 3e 20 4d 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f > M, const vecto
0130: 72 3c 64 6f 75 62 6c 65 3e 26 20 56 20 29 0a 7b r<double>& V ).{
0140: 0a 09 76 65 63 74 6f 72 3c 64 6f 75 62 6c 65 3e ..vector<double>
0150: 20 41 28 56 29 3b 0a 09 66 6f 72 28 69 6e 74 20 A(V);..for(int
0160: 69 3d 30 3b 20 69 3c 6e 3b 20 2b 2b 69 29 0a 09 i=0; i<n; ++i)..
0170: 7b 0a 09 09 2f 2f 20 70 69 76 6f 74 0a 09 09 69 {...// pivot...i
0180: 66 28 20 4d 5b 69 5d 5b 69 5d 20 3d 3d 20 30 20 f( M[i][i] == 0
0190: 29 0a 09 09 09 66 6f 72 28 69 6e 74 20 6a 3d 69 )....for(int j=i
01a0: 2b 31 3b 20 6a 3c 6e 3b 20 2b 2b 6a 29 0a 09 09 +1; j<n; ++j)...
01b0: 09 09 69 66 28 20 4d 5b 6a 5d 5b 69 5d 20 21 3d ..if( M[j][i] !=
01c0: 20 30 20 29 0a 09 09 09 09 09 7b 73 77 61 70 28 0 )......{swap(
01d0: 4d 5b 69 5d 2c 20 4d 5b 6a 5d 29 3b 20 73 77 61 M[i], M[j]); swa
01e0: 70 28 41 5b 69 5d 2c 20 41 5b 6a 5d 29 3b 20 62 p(A[i], A[j]); b
01f0: 72 65 61 6b 3b 7d 0a 09 09 69 66 28 20 4d 5b 69 reak;}...if( M[i
0200: 5d 5b 69 5d 20 3d 3d 20 30 20 29 0a 09 09 09 74 ][i] == 0 )....t
0210: 68 72 6f 77 20 22 6e 6f 20 61 6e 73 65 72 22 3b hrow "no anser";
0220: 0a 0a 09 09 2f 2f 20 4d 5b 69 5d 5b 69 5d 20 3c ....// M[i][i] <
0230: 2d 2d 20 31 0a 09 09 64 6f 75 62 6c 65 20 70 20 -- 1...double p
0240: 3d 20 4d 5b 69 5d 5b 69 5d 3b 0a 09 09 66 6f 72 = M[i][i];...for
0250: 28 69 6e 74 20 6a 3d 69 3b 20 6a 3c 6e 3b 20 2b (int j=i; j<n; +
0260: 2b 6a 29 0a 09 09 09 4d 5b 69 5d 5b 6a 5d 20 2f +j)....M[i][j] /
0270: 3d 20 70 3b 0a 09 09 41 5b 69 5d 20 2f 3d 20 70 = p;...A[i] /= p
0280: 3b 0a 0a 09 09 2f 2f 20 4d 5b 2a 5d 5b 69 5d 20 ;....// M[*][i]
0290: 3c 2d 2d 20 30 0a 09 09 66 6f 72 28 69 6e 74 20 <-- 0...for(int
02a0: 6a 3d 30 3b 20 6a 3c 6e 3b 20 2b 2b 6a 29 20 69 j=0; j<n; ++j) i
02b0: 66 28 6a 21 3d 69 29 0a 09 09 7b 0a 09 09 09 64 f(j!=i)...{....d
02c0: 6f 75 62 6c 65 20 72 20 3d 20 4d 5b 6a 5d 5b 69 ouble r = M[j][i
02d0: 5d 3b 0a 09 09 09 66 6f 72 28 69 6e 74 20 6b 3d ];....for(int k=
02e0: 69 3b 20 6b 3c 6e 3b 20 2b 2b 6b 29 0a 09 09 09 i; k<n; ++k)....
02f0: 09 4d 5b 6a 5d 5b 6b 5d 20 2d 3d 20 4d 5b 69 5d .M[j][k] -= M[i]
0300: 5b 6b 5d 20 2a 20 72 3b 0a 09 09 09 41 5b 6a 5d [k] * r;....A[j]
0310: 20 2d 3d 20 41 5b 69 5d 20 2a 20 72 3b 0a 09 09 -= A[i] * r;...
0320: 7d 0a 09 7d 0a 09 72 65 74 75 72 6e 20 41 3b 0a }..}..return A;.
0330: 7d 0a }.