挑战程序竞赛系列（43）：4.1矩阵 高斯消元

详细代码可以fork下Github上leetcode项目，不定期更新。

练习题如下：

POJ 2345: Central heatingPOJ 3532: ResistancePOJ 3526: The Teacher’s Side of Math

POJ 2345: Central heating

知识点：高斯消元法，关于高斯消元法可以参考博文：

博文1： http://www.cppblog.com/menjitianya/archive/2014/06/08/207226.html

博文2： http://www.hankcs.com/program/algorithm/poj-2345-heating-central.html

我的理解： 它的核心在于消元，体现在迭代的过程当中，具体如下，依次遍历每一行，意味着消元消到了第i个变量，此时把后续行和第i个变量有关的全部消去，这样一来，第i+1行的所有变量数减一。

那么自然地，遍历到最后一行时，只剩一个变量，自然就出解了，接着把这个解慢慢往前回代，就能得到所有解。

此题思路：先将输入处理为01矩阵。题目用例中，如果第i个人管理第j个阀门，则记matrix[j][i] = 1，否则为0。然后目标是让所有闸门都开，也就是B向量都为1。

接着：把消元相减看成异或，乘法看成与运算，over。

代码如下：

import java.io.BufferedReader; import java.io.File; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.StringTokenizer; public class Main{ String INPUT = "./data/judge/201708/P2345.txt"; public static void main(String[] args) throws IOException { new Main().run(); } static final int MAX_N = 255; int[][] matrix = new int[MAX_N][MAX_N]; void solve() { while (more()){ int n = ni(); for (int i = 0; i < n; ++i){ int j = ni(); while (j != -1){ j--; matrix[j][i] = 1; matrix[j][n] = 1; j = ni(); } } int[] ans = gauss(matrix, n); StringBuilder sb = new StringBuilder(); for (int i = 0; i < ans.length; ++i){ if (ans[i] == 1){ sb.append(" " + (i + 1)); } } out.println(sb.deleteCharAt(0).toString()); } } /*******************高斯消元法*********************/ public int[] gauss(int[][] matrix, int n){ int[] ans = new int[n]; for (int i = 0; i < n; ++i){ int row = i; for (int j = i; j < n; ++j){ if (matrix[j][i] > matrix[row][i]){ row = j; } } swap(matrix, i, row); for (int j = i + 1; j < n; ++j){ if (matrix[j][i] == 1){ for (int k = i; k <= n; ++k){ matrix[j][k] ^= matrix[i][k]; } } } } for (int i = n - 1; i >= 0; --i){ ans[i] = matrix[i][n]; for (int j = i - 1; j >= 0; --j){ matrix[j][n] ^= (ans[i] & matrix[j][i]); } } return ans; } public void swap(int[][] matrix, int i, int j){ int n = matrix[0].length; for (int col = 0; col < n; ++col){ int tmp = matrix[i][col]; matrix[i][col] = matrix[j][col]; matrix[j][col] = tmp; } } FastScanner in; PrintWriter out; void run() throws IOException { boolean oj; try { oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode"); } catch (Exception e) { oj = System.getProperty("ONLINE_JUDGE") != null; } InputStream is = oj ? System.in : new FileInputStream(new File(INPUT)); in = new FastScanner(is); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if (!oj){ System.out.println("[" + (System.currentTimeMillis() - s) + "ms]"); } } public boolean more(){ return in.hasNext(); } public int ni(){ return in.nextInt(); } public long nl(){ return in.nextLong(); } public double nd(){ return in.nextDouble(); } public String ns(){ return in.nextString(); } public char nc(){ return in.nextChar(); } class FastScanner { BufferedReader br; StringTokenizer st; boolean hasNext; public FastScanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is)); hasNext = true; } public String nextToken() { while (st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(br.readLine()); } catch (Exception e) { hasNext = false; return "##"; } } return st.nextToken(); } String next = null; public boolean hasNext(){ next = nextToken(); return hasNext; } public int nextInt() { if (next == null){ hasNext(); } String more = next; next = null; return Integer.parseInt(more); } public long nextLong() { if (next == null){ hasNext(); } String more = next; next = null; return Long.parseLong(more); } public double nextDouble() { if (next == null){ hasNext(); } String more = next; next = null; return Double.parseDouble(more); } public String nextString(){ if (next == null){ hasNext(); } String more = next; next = null; return more; } public char nextChar(){ if (next == null){ hasNext(); } String more = next; next = null; return more.charAt(0); } } }

POJ 3532: Resistance

心累，学完数学还要学物理么，这里就不再讲解电路的知识了，有兴趣的可以参考博文： http://www.hankcs.com/program/algorithm/poj-3532-resistance.html

以及博文： http://blog.csdn.net/u012139398/article/details/41345607

我重在实现高斯算法：

import java.io.BufferedReader; import java.io.File; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.StringTokenizer; public class Main { String INPUT = "./data/judge/201708/P3532.txt"; public static void main(String[] args) throws IOException { new Main().run(); } static final int MAX_N = 100; static final double EPS = 1E-8; int N; void solve() { while (more()){ N = ni(); int M = ni(); double[][] matrix = new double[MAX_N][MAX_N]; for (int i = 0; i < M; ++i){ int x = ni(); int y = ni(); int r = ni(); --x; --y; double s = 1.0 / r; matrix[x][x] += s; matrix[y][y] += s; matrix[x][y] -= s; matrix[y][x] -= s; } N++; matrix[0][N] = 1.0; matrix[N - 2][N] = -1.0; matrix[N - 1][N - 2] = 1.0; out.printf("%.2f\n", gaussian(matrix)); } } public double gaussian(double[][] cal){ int n = N; for (int i = 0; i < n; ++i){ int r; for (r = i; r < n; ++r){ if (Math.abs(cal[r][i]) >= EPS){ break; } } if (r == n) continue; // 无解直接跳过 swap(cal, i, r); for (int j = i + 1; j <= n; ++j) cal[i][j] /= cal[i][i]; cal[i][i] = 1.0; for (int j = 0; j < n; ++j){ if (i != j){ for (int k = i + 1; k <= n; ++k){ cal[j][k] -= (cal[j][i] * cal[i][k]); } cal[j][i] = 0.0; } } } return cal[0][N] / cal[0][0]; } public void swap(double[][] matrix, int i, int j){ int n = matrix[0].length; for (int col = 0; col < n; ++col){ double tmp = matrix[i][col]; matrix[i][col] = matrix[j][col]; matrix[j][col] = tmp; } } FastScanner in; PrintWriter out; void run() throws IOException { boolean oj; try { oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode"); } catch (Exception e) { oj = System.getProperty("ONLINE_JUDGE") != null; } InputStream is = oj ? System.in : new FileInputStream(new File(INPUT)); in = new FastScanner(is); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if (!oj){ System.out.println("[" + (System.currentTimeMillis() - s) + "ms]"); } } public boolean more(){ return in.hasNext(); } public int ni(){ return in.nextInt(); } public long nl(){ return in.nextLong(); } public double nd(){ return in.nextDouble(); } public String ns(){ return in.nextString(); } public char nc(){ return in.nextChar(); } class FastScanner { BufferedReader br; StringTokenizer st; boolean hasNext; public FastScanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is)); hasNext = true; } public String nextToken() { while (st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(br.readLine()); } catch (Exception e) { hasNext = false; return "##"; } } return st.nextToken(); } String next = null; public boolean hasNext(){ next = nextToken(); return hasNext; } public int nextInt() { if (next == null){ hasNext(); } String more = next; next = null; return Integer.parseInt(more); } public long nextLong() { if (next == null){ hasNext(); } String more = next; next = null; return Long.parseLong(more); } public double nextDouble() { if (next == null){ hasNext(); } String more = next; next = null; return Double.parseDouble(more); } public String nextString(){ if (next == null){ hasNext(); } String more = next; next = null; return more; } public char nextChar(){ if (next == null){ hasNext(); } String more = next; next = null; return more.charAt(0); } } }

需要注意的细节：进行归一化时，切记不要把当前变量给归一了，否则bug，所以有循环for从i+1开始，同理在消元时也从i+1开始。

POJ 3526: The Teacher’s Side of Math

此题的trick在于如何表达不同的 αiβj ，很巧妙，因为在根号下，我们把式子转化为：

αimβjn

可以看出，i在(0,m)之间时，alpha一定为无理数，此题就是枚举出所有无理数之前的系数，让这些系数之和加起来等于0即可。

所以当i>m时，可以求出无理数之前的整数，比如：

αim=αi/m⋅αimodmm

i/m表示取下整哟，这样我们就可以把所有的 α,β 的无理数组合遍历出来，还恰好是：n*m + 1个方程。

你还可以参考：http://www.hankcs.com/program/algorithm/poj-3526-teacher-s-side-of-math-the.html

他的思路：

首先题目的隐含条件是，多项式最高次数一定为m*n。将(a1/m + b1/n)k二项展开后，除了最高次数项被题目限定为1之外，各项的系数和必须为0。以各项系数为变量，列出线性方程组，然后高斯消元求解即可。

JAVA代码如下：

import java.io.BufferedReader; import java.io.File; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.StringTokenizer; public class Main{ String INPUT = "./data/judge/201708/P3526.txt"; public static void main(String[] args) throws IOException { new Main().run(); } static final double EPS = 1E-8; static final int MAX_N = 20 + 8; int[][] matrix = new int[MAX_N][MAX_N]; int M, N, SIZE; void solve() { int[][] C = new int[MAX_N][MAX_N]; C[0][0] = 1; for (int i = 1; i < MAX_N; ++i) { C[i][0] = 1; C[i][i] = 1; for (int j = 1; j < i; ++j) { C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } } while (true) { int a = ni(); int m = ni(); int b = ni(); int n = ni(); M = m; N = n; if (a + m + b + n == 0) break; SIZE = n * m + 1; double[][] matrix = new double[SIZE][SIZE + 1]; matrix[0][0] = matrix[0][SIZE] = 1; for (int i = 0; i < SIZE; ++i) { for (int j = 0; j <= i; ++j) { matrix[to_index(j % m, (i - j) % n)][i < n * m ? i + 1 : 0] += C[i][j] * Math.pow((double) a, j / m) * Math.pow((double) b, (i - j) / n); } } gaussian(matrix); StringBuilder sb = new StringBuilder(); sb.append("1"); for (int i = SIZE - 1; i >= 1; --i) { sb.append(" " + (int)(round(ans[i]))); } out.println(sb.toString()); } } double round(double x) { return x >= 0.0 ? Math.floor(x + 0.5) : Math.ceil(x - 0.5); } double[] ans; public boolean gaussian(double[][] matrix) { ans = new double[SIZE]; for (int i = 0; i < SIZE; ++i) { int row = i; for (int j = i; j < SIZE; ++j) { if (Math.abs(matrix[j][i]) > Math.abs(matrix[row][i])) { row = j; } } swap(matrix, i, row); if (Math.abs(matrix[i][i]) <= EPS) return false; for (int j = i + 1; j < SIZE + 1; ++j) matrix[i][j] /= matrix[i][i]; matrix[i][i] = 1; for (int j = 0; j < SIZE; ++j) { if (i != j) { for (int k = i + 1; k < SIZE + 1; ++k) { matrix[j][k] -= (matrix[j][i] * matrix[i][k]); } matrix[j][i] = 0.0; } } } for (int i = 0; i < SIZE; ++i) { ans[i] = matrix[i][SIZE]; } return true; } public void swap(double[][] matrix, int i, int j) { int n = matrix[0].length; for (int col = 0; col < n; ++col) { double tmp = matrix[i][col]; matrix[i][col] = matrix[j][col]; matrix[j][col] = tmp; } } public int to_index(int i, int j) { return i * N + j + 1; } FastScanner in; PrintWriter out; void run() throws IOException { boolean oj; try { oj = !System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode"); } catch (Exception e) { oj = System.getProperty("ONLINE_JUDGE") != null; } InputStream is = oj ? System.in : new FileInputStream(new File(INPUT)); in = new FastScanner(is); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if (!oj) { System.out.println("[" + (System.currentTimeMillis() - s) + "ms]"); } } public boolean more() { return in.hasNext(); } public int ni() { return in.nextInt(); } public long nl() { return in.nextLong(); } public double nd() { return in.nextDouble(); } public String ns() { return in.nextString(); } public char nc() { return in.nextChar(); } class FastScanner { BufferedReader br; StringTokenizer st; boolean hasNext; public FastScanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is)); hasNext = true; } public String nextToken() { while (st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(br.readLine()); } catch (Exception e) { hasNext = false; return "##"; } } return st.nextToken(); } String next = null; public boolean hasNext() { next = nextToken(); return hasNext; } public int nextInt() { if (next == null) { hasNext(); } String more = next; next = null; return Integer.parseInt(more); } public long nextLong() { if (next == null) { hasNext(); } String more = next; next = null; return Long.parseLong(more); } public double nextDouble() { if (next == null) { hasNext(); } String more = next; next = null; return Double.parseDouble(more); } public String nextString() { if (next == null) { hasNext(); } String more = next; next = null; return more; } public char nextChar() { if (next == null) { hasNext(); } String more = next; next = null; return more.charAt(0); } } }

这模版有点叼啊，把把第一，只怪用JAVA写的太少了吧。