洛谷P4035[JSOI2008]球形空间生成器（高斯消元法/模拟退火算法）

整理的算法模板合集&＃xff1a; ACM模板

点我看算法全家桶系列&＃xff01;&＃xff01;&＃xff01;

实际上是一个全新的精炼模板整合计划

数据范围只开到了10&＃xff0c;而且是经典的力学结构&＃xff0c;所以我们可以用模拟退火&＃xff0c;可以做一下 $n$ 维的正交分解hhh&＃xff0c;经典物理题。

然后实际上本题就是一个高斯消元模板题

apple pencil用习惯了&＃xff0c;普通的笔写起来&＃xff0c;字丑见谅

我用的是普通的高斯消元模板&＃xff0c;因为听说高斯 - 约旦消元法有可能会被卡掉&＃xff0c;所以学了&＃xff0c;但是一直不敢用QWQ

#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef int itn;
typedef pair<int, int>PII;
const int N &＃61; 2007, mod &＃61; 1e9 &＃43; 7, INF &＃61; 2.1e9;
const double eps &＃61; 1e-8;int n, m;
double b[N][N];//增广矩阵
double a[N][N];int guass(double a[][N])
{int c;//当前最左边的一列int r;//当前最上面的一行for(c &＃61; 1, r &＃61; 1; c <&＃61; n; &＃43;&＃43; c){int t &＃61; r;for(int i &＃61; r &＃43; 1; i <&＃61; n; &＃43;&＃43; i){if(fabs(a[i][c]) > fabs(a[t][c]))t &＃61; i;}if(fabs(a[t][c]) < eps)//等于0就下一个continue;//换到第一行&＃xff08;最上面的一行&＃xff09;for(int i &＃61; c; i <&＃61; n &＃43; 1; &＃43;&＃43; i)swap(a[t][i], a[r][i]);//把该行第一个数变成 1&＃xff08;该行每一列都/&＃61;第c列的值&＃xff09;for(int i &＃61; n &＃43; 1; i >&＃61; c; -- i)a[r][i] /&＃61; a[r][c];//中间所有列&＃xff08;所有项&＃xff09;全部消掉for(int i &＃61; r &＃43; 1; i <&＃61; n; &＃43;&＃43; i)if(fabs(a[i][c]) > eps)for(int j &＃61; n &＃43; 1; j >&＃61; c; -- j)a[i][j] -&＃61; a[r][j] * a[i][c];r &＃43;&＃43; ;}if(r <&＃61; n){for(int i &＃61; r; i <&＃61; n; &＃43;&＃43; i)if(fabs(a[i][n &＃43; 1]) > eps)//非零&＃xff0c;无解return 2;return 1;//无穷多组解}//回代//行最简形矩阵for(int i &＃61; n; i >&＃61; 1; -- i)for(int j &＃61; i &＃43; 1; j <&＃61; n &＃43; 1; &＃43;&＃43; j)a[i][n &＃43; 1] -&＃61; a[j][n &＃43; 1] * a[i][j]; return 0;
}int main()
{scanf("%d", &n);for(int i &＃61; 1; i <&＃61; n &＃43; 1; &＃43;&＃43; i)for(int j &＃61; 1; j <&＃61; n; &＃43;&＃43; j)scanf("%lf", &a[i][j]);for(int i &＃61; 1; i <&＃61; n; &＃43;&＃43; i)for(int j &＃61; 1; j <&＃61; n; &＃43;&＃43; j){b[i][j] &＃61; 2 * (a[i][j] - a[i &＃43; 1][j]);b[i][n &＃43; 1] &＃43;&＃61; a[i][j] * a[i][j] - a[i &＃43; 1][j] * a[i &＃43; 1][j];}guass(b);for(int i &＃61; 1; i < n; &＃43;&＃43; i)printf("%.3f ", b[i][n &＃43; 1]);printf("%.3f\n", b[n][n &＃43; 1]);return 0;
}