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

## POJ 2345: Central heating

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
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 {
StringTokenizer st;
boolean hasNext;

public FastScanner(InputStream is) throws IOException {
hasNext = true;
}

public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
} 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

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
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 {
StringTokenizer st;
boolean hasNext;

public FastScanner(InputStream is) throws IOException {
hasNext = true;
}

public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
} 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 3526: The Teacher’s Side of Math

αimβjn

\alpha^{\frac{i}{m}}\beta^{\frac{j}{n}}

αim=αi/m⋅αimodmm

\alpha^{\frac{i}{m}} = \alpha^{i / m}\cdot\alpha^{\frac{i\mod m}{m}}

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

JAVA代码如下：

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
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 {
StringTokenizer st;
boolean hasNext;

public FastScanner(InputStream is) throws IOException {
hasNext = true;
}

public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
} 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);
}
}
}

0 条评论

• ### 远程办公经验为0，如何将日常工作平滑过度到线上?

我是一名创业者，我的公司（深圳市友浩达科技有限公司）在2018年8月8日开始运营，现在还属于微型公司。这个春节假期，我一直十分关注疫情动向，也非常关心其对公司带来的影响。

• ### 数据中台，概念炒作还是另有奇效？ | TVP思享

作者简介：史凯，花名凯哥，腾讯云最具价值专家TVP，ThoughtWorks数据智能业务总经理。投身于企业数字化转型工作近20年。2000年初，在IBM 研发企业级中间件，接着加入埃森哲，为大型企业提供信息化架构规划，设计，ERP，云平台，数据仓库构建等技术咨询实施服务，随后在EMC负责企业应用转型业务，为企业提供云迁移，应用现代化服务。现在专注于企业智能化转型领域，是数据驱动的数字化转型的行业布道者，数据中台的推广者，精益数据创新体系的创始人，2019年荣获全球Data IQ 100人的数据赋能者称号，创业邦卓越生态聚合赋能官TOP 5。2019年度数字化转型专家奖。打造了行业第一个数据创新的数字化转型卡牌和工作坊。创建了精益数据创新方法论体系构建数据驱动的智能企业，并在多个企业验证成功，正在向国内外推广。

• ### 扩展 Kubernetes 之 CRI

使用 cri-containerd 的调用流程更为简洁, 省去了上面的调用流程的 1，2 两步

• ### 扩展 Kubernetes 之 Kubectl Plugin

kubectl 功能非常强大, 常见的命令使用方式可以参考 kubectl --help，或者这篇文章

• ### 多种登录方式定量性能测试方案

最近接到到一个测试任务，某服务提供了两种登录方式：1、账号密码登录；2、手机号+验证码登录。要对这两种登录按照一定的比例进行压测。

• ### 线程安全类在性能测试中应用

首先验证接口参数签名是否正确，然后加锁去判断订单信息和状态，处理用户增添VIP时间事务，成功之后释放锁。锁是针对用户和订单的分布式锁，使用方案是用的redis。

• ### 使用CDN(jsdelivr) 优化博客访问速度

PS: 此篇文章适用于 使用 Github pages 或者 coding pages 的朋友,其他博客也类似.

• ### 扩展 Kubernetes 之 CNI

Network Configuration 是 CNI 输入参数中最重要当部分, 可以存储在磁盘上

• ### 聚焦【技术应变力】云加社区沙龙online重磅上线！

云加社区结合特殊时期热点，挑选备受关注的音视频流量暴增、线下业务快速转线上、紧急上线防疫IoT应用等话题，邀请众多业界专家，为大家提供连续十一天的干货分享。从视野、预判、应对等多角度，帮助大家全面提升「技术应变力」！

• ### 京东购物小程序购物车性能优化实践

它是小程序开发工具内置的一个可视化监控工具，能够在 OS 级别上实时记录系统资源的使用情况。