http://acm.hdu.edu.cn/showproblem.php?pid=3359
题目的意思是，由矩阵A生成矩阵B的方法是:
以a[i][j]为中心的，哈曼顿距离不大于dis的数字的总和 / 个数，就是矩阵B的b[i][j]
现在给出B，要求A
那么我们设A矩阵为a[1][1], a[1][2], a[1][3].....
那么对于每一个b[i][j]我们有b[i][j] = (a[1][1] + a[1][2] + ... + ) / cnt
所以这样可以建议一条方程，然后guass求解。
注意题目的输出格式，printf("%8.2lf")后，不需要加空格。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 2e2 + ;
const double eps = 1e-;
class GaussMatrix {
public:
double a[maxn][maxn];
int equ, val; //方程个数（行），和变量个数（列），其中第val个是b值，不能取
void swapRow(int rowOne, int rowTwo) {
for (int i = ; i <= val; ++i) {
swap(a[rowOne][i], a[rowTwo][i]);
}
}
void swapCol(int colOne, int colTwo) {
for (int i = ; i <= equ; ++i) {
swap(a[i][colOne], a[i][colTwo]);
}
}
bool same(double x, double y) {
return fabs(x - y) < eps;
}
int guass() {
int k, col;
for (k = , col = ; k <= equ && col < val; ++k, ++col) { //不能取到第val个
int maxRow = k; //选出列最大值，误差最小
for (int i = k + ; i <= equ; ++i) {
if (fabs(a[i][col]) > fabs(a[maxRow][col])) {
maxRow = i;
}
}
if (same(a[maxRow][col], )) {
--k;
continue;
}
if (maxRow != k) swapRow(k, maxRow);
for (int i = col + ; i <= val; ++i) { //约去系数
a[k][i] /= a[k][col];
}
a[k][col] = 1.0; //第一个就要变成1了，然后下面和上面的变成0
for (int i = ; i <= equ; ++i) {
if (i == k) continue; //当前这行，不操作
for (int j = col + ; j <= val; ++j) {
a[i][j] -= a[i][col] * a[k][j];
}
a[i][col] = 0.0;
}
// debug();
}
for (k; k <= equ; ++k) {
if (!same(a[k][val], )) return -; //方程无解
}
return val - k; //自由变量个数
}
void debug() {
for (int i = ; i <= equ; ++i) {
for (int j = ; j <= val; ++j) {
printf("%6.2lf ", a[i][j]);
}
printf("\n");
}
printf("*******************************************\n\n");
}
}arr;
int dis;
double mp[maxn][maxn];
int vis[maxn][maxn], DFN;
int n, m;
int tonext[][] = {{, }, {, }, {, -}, {-, }};
struct bfsNode {
int cnt, x, y;
bfsNode(int _cnt, int _x, int _y) {
cnt = _cnt, x = _x, y = _y;
}
};
queue<struct bfsNode>que;
int toHash(int x, int y) {
return x * max(n, m) + y;
}
void init(int row, int col, int which) {
++DFN;
while (!que.empty()) que.pop();
arr.a[which][toHash(row, col)] = 1.0;
que.push(bfsNode(, row, col));
vis[row][col] = DFN;
int has = ;
while (!que.empty()) {
struct bfsNode t = que.front();
que.pop();
if (t.cnt + > dis) break;
for (int i = ; i < ; ++i) {
int tx = t.x + tonext[i][], ty = t.y + tonext[i][];
if (tx >= && tx <= n && ty >= && ty <= m && vis[tx][ty] != DFN) {
vis[tx][ty] = DFN;
arr.a[which][toHash(tx, ty)] = 1.0;
que.push(bfsNode(t.cnt + , tx, ty));
has++;
}
}
}
arr.a[which][toHash(n, m) + ] = mp[row][col] * has;
}
void work() {
n = arr.equ, m = arr.val;
for (int i = ; i <= n; ++i) {
for (int j = ; j <= m; ++j) {
scanf("%lf", &mp[i][j]);
}
}
int which = ;
for (int i = ; i <= n; ++i) {
for (int j = ; j <= m; ++j) {
init(i, j, ++which);
}
}
arr.equ = which;
arr.val = toHash(n, m) + ;
// arr.debug();
arr.guass();
// arr.debug();
int to = ;
for (int i = ; i <= n; ++i) {
for (int j = ; j <= m; ++j) {
printf("%8.2lf", arr.a[to++][toHash(n, m) + ]);
}
printf("\n");
}
}
int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
while (scanf("%d%d%d", &arr.val, &arr.equ, &dis) != EOF && arr.val + arr.equ + dis) {
if (!flag) printf("\n");
flag = false;
work();
memset(&arr, , sizeof arr);
}
return ;
}
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 1e2 + ;
const double eps = 1e-;
class GaussMatrix {
public:
double a[maxn][maxn], x[maxn];
int equ, val; //方程个数（行），和变量个数（列），其中第val个是b值，不能取
void swapRow(int rowOne, int rowTwo) {
for (int i = ; i <= val; ++i) {
swap(a[rowOne][i], a[rowTwo][i]);
}
}
void swapCol(int colOne, int colTwo) {
for (int i = ; i <= equ; ++i) {
swap(a[i][colOne], a[i][colTwo]);
}
}
bool same(double x, double y) {
return fabs(x - y) < eps;
}
int guass() {
int k, col;
for (k = , col = ; k <= equ && col < val; ++k, ++col) { //不能取到第val个
int maxRow = k; //选出列最大值，误差最小
for (int i = k + ; i <= equ; ++i) {
if (fabs(a[i][col]) > fabs(a[maxRow][col])) {
maxRow = i;
}
}
if (same(a[maxRow][col], )) {
--k;
continue;
}
if (maxRow != k) swapRow(k, maxRow);
for (int i = col + ; i <= val; ++i) { //约去系数
a[k][i] /= a[k][col];
}
a[k][col] = 1.0; //第一个就要变成1了，然后下面和上面的变成0
for (int i = ; i <= equ; ++i) {
if (i == k) continue; //当前这行，不操作
for (int j = col + ; j <= val; ++j) {
a[i][j] -= a[i][col] * a[k][j];
}
a[i][col] = 0.0;
}
debug();
}
for (k; k <= equ; ++k) {
if (!same(a[k][val], )) return -; //方程无解
}
return val - k; //自由变量个数
}
void debug() {
for (int i = ; i <= equ; ++i) {
for (int j = ; j <= val; ++j) {
printf("%6.2lf ", a[i][j]);
}
printf("\n");
}
printf("*******************************************\n\n");
}
}arr;
void work() {
// arr.equ = 3, arr.val = 5;
// arr.a[1][1] = 1, arr.a[1][2] = 2, arr.a[1][3] = -1, arr.a[1][4] = 1, arr.a[1][5] = 2;
// arr.a[2][1] = 2, arr.a[2][2] = -1, arr.a[2][3] = 1, arr.a[2][4] = -3, arr.a[2][5] = -1;
// arr.a[3][1] = 4, arr.a[3][2] = 3, arr.a[3][3] = -1, arr.a[3][4] = -1, arr.a[3][5] = 3;
// int res = arr.guass();
// cout << res << endl; // arr.equ = 4, arr.val = 3 + 1;
// arr.a[1][1] = 2, arr.a[1][2] = 3, arr.a[1][3] = 1, arr.a[1][4] = 4;
// arr.a[2][1] = 1, arr.a[2][2] = -2, arr.a[2][3] = 4, arr.a[2][4] = -5;
// arr.a[3][1] = 3, arr.a[3][2] = 8, arr.a[3][3] = -2, arr.a[3][4] = 13;
// arr.a[4][1] = 4, arr.a[4][2] = -1, arr.a[4][3] = 9, arr.a[4][4] = -6;
// cout << arr.guass() << endl; // arr.equ = 3, arr.val = 3 + 1;
// arr.a[1][1] = 2, arr.a[1][2] = 3, arr.a[1][3] = 1, arr.a[1][4] = 16;
// arr.a[2][1] = 1, arr.a[2][2] = 5, arr.a[2][3] = 2, arr.a[2][4] = 23;
// arr.a[3][1] = 3, arr.a[3][2] = 4, arr.a[3][3] = 5, arr.a[3][4] = 33;
// cout << arr.guass() << endl; // arr.equ = 3, arr.val = 4;
// arr.a[1][1] = 2, arr.a[1][2] = 3, arr.a[1][3] = -1, arr.a[1][4] = 2;
// arr.a[2][1] = 3, arr.a[2][2] = -2, arr.a[2][3] = 1, arr.a[2][4] = 2;
// arr.a[3][1] = 1, arr.a[3][2] = -5, arr.a[3][3] = 2, arr.a[3][4] = 1;
// cout << arr.guass() << endl; arr.equ = , arr.val = ;
arr.a[][] = , arr.a[][] = , arr.a[][] = , arr.a[][] = ;
arr.a[][] = , arr.a[][] = , arr.a[][] = , arr.a[][] = ;
arr.a[][] = , arr.a[][] = , arr.a[][] = , arr.a[][] = ;
cout << arr.guass() << endl;
}
int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
高斯消元模板 && 题目