高斯消元
一，什么是高斯消元？
用来解决需要解方程组的题目时所用的一种算法。
适用于以下该种形式的式子：
其中,\(a_i\)为常数，\(k_{i,j}\)为系数，\(x_{i,j}\)为未知数,且对于所有\(i,j\)都满足\(1<=i,j<=n\)。
显然，在这个方程组中有\(n\)个未知数和\(n\)个n元一次方程，易知，当方程组中的方程两两不满足倍数关系时,这个方程组必定有解。
求解这个方程组的朴素方法就是高斯消元。
虽然听起来很高端，实际上就是我们常用的加减消元罢了
于是，有了这样一个\(O(n^3)\)的做法。
1.选择一个尚未被选过的未知数作为主元，选择一个包含这个主元的方程。
2.将这个方程主元的系数化为1。
3.通过加减消元，消掉其它方程中的这个未知数。
4.重复以上步骤，直到把每一行都只有一项有系数。
这个方法和传统的高斯消元有所不同，我们称之为约旦消元法，相对于传统的高斯消元，约旦消元法的精度更好、代码更简单，没有回带的过程。也是我在算法竞赛中使用的算法，感谢这篇博客给予的启发。
我个人也对这个算法进行了一点小小的优化，板子放在下面帮助理解。
inline void gauss(int n){
int mx;
f1(i,1,n){
mx=i;
f1(j,i+1,n+1)if(fabs(f[j][i])>fabs(f[mx][i]))mx=j;//查找第i位系数最大的方程
if(mx!=i)swap(f[i],f[mx]);//将找到的第i位系数最大的方程放在第i个位置
f2(j,n+1,i)f[i][j]/=f[i][i];//将第i个方程每一位的系数都除以第i位系数，使得第i位系数化为1
f1(j,1,n)if(i!=j)f2(k,n+1,i)
f[j][k]-=f[j][i]*f[i][k];//加减消元，由于上面已经除过系数了，这里的f[j][i]就是第j个方程相对于第i个方程的倍数。
}
}
最终，完成高斯消元后，对于第\(i\)个方程，它的第\(n+1\)位即为第\(i\)个未知数的值。
二，进阶应用
如果高斯消元只能用来解方程的话，那么它就不可能作为数论一项重要考点出现在算法竞赛中，接下来就来看看它的进阶用法。
想象一种情形，每个点都有一种特殊权值，这种权值由这个点的邻接点权值决定，每个点间权值的关联关系不同。现在给你一张有\(n\)个点\(m\)条边的无向连通图，告知你相连的每一对点直接的权值关系，要求你求出每一个点的权值。
是不是感觉有点摸不清头脑？
没关系，让我们来简化下题目，将点的权值设为\(x_i\),将题目所说的点\(i\)和点\(j\)间的关联关系看作\(k_{i,j}\)。
那么对于一个点的权值\(x_i\),我们可以得到这样一个表达式。
还是很迷糊？来把所有未知数放到一边，把求和拆出来
\[k_{i,j_1}*x_{j_1}+k_{i,j_2}*x_{j_2}+\cdots+k_{i,j_n}*x_{j_n}-x_i=0 \]！这个熟悉的式子，没错，是高斯消元。
你可能注意到了，这里的\(j\)枚举到了除\(i\)外的每一项直到\(n\)，这是因为，对于任何一个点\(j\)，如果与\(x_i\)相连，那么这里\(k_{i,j}\)就是两点间的关系，而如果不相连，直接令\(k_{i,j}\)等于\(0\)即可。同样，式子中最后一项的系数\(-1\)同样可以看作\(k\)。到这里，这个式子就和开头的公式完全一致了。
更让人激动的是，而这样的式子我们有\(n\)个！
故而可以使用高斯消元轻松求出每一个点的权值。
现在来想一个问题，在常见的题目中，有哪类题中点的权值与相邻点有关呢？
期望！！！
没错，高斯消元常常与用于解决图论中的期望题，所以当你看到一道有关图论期望题目，而\(n\)又很小时，它很可能就需要高斯消元来解决。
让我们来看几道例题加深理解。
例题
题目描述
给定一个 \(n\) 个点 \(m\) 条边的无向连通图，顶点从 \(1\) 编号到 \(n\)，边从 \(1\) 编号到 \(m\)。
小 Z 在该图上进行随机游走，初始时小 Z 在 \(1\) 号顶点，每一步小 Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 \(n\) 号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这 \(m\) 条边进行编号，使得小 Z 获得的总分的期望值最小。
输入格式
第一行是两个整数，分别表示该图的顶点数 \(n\) 和边数 \(m\)。
接下来 \(m\) 行每行两个整数 \(u,v\)，表示顶点 \(u\) 与顶点 \(v\) 之间存在一条边。
数据规模与约定
- 对于 \(30\%\) 的数据，保证 \(n\leq 10\)。
- 对于 \(100\%\) 的数据，保证 \(2\leq n \leq 500\)， \(1 \leq m \leq 125000\)，\(1 \leq u, v \leq n\)，给出的图无重边和自环，且从 \(1\) 出发可以到达所有的节点。
可以说是这一类型题的板子了。
非常明显，要求总分最少，就要使得期望经过次数越高的边的分数越低。
又容易想到，对于点\(i\)和点\(j\)间的一条边\(v\)的期望经过次数\(p[v]\),有
其中，\(deg[i]\)表示点\(i\)的度，（也就是点\(i\)所连边的数量），\(g[i]\)为点\(i\)的期望经过次数。
显然，当我们知道所有点的期望经过次数后，边的期望经过次数就可以直接\(O(m)\)的求出来了。
于是问题转化为求点的期望经过次数。
很容易列出这样一个式子。
突然发现和上面那个式子一模一样。
于是这题就这样轻松解决掉了。
然而并没有，还要一些细节要处理。
首先，未知数应当只有n-1 一个，因为到达点n就会停止，那么其他点是无法通过点n到达的。
因此不能考虑点n的贡献。
还有一个小细节，由于是从点1开始游走，那么点1的期望值应当加1，否则会出错。
Coding:
#include<bits/stdc++.h>
#define double long double
#define N 505
#define f1(i,n,m) for(int i=n;i<=m;++i)
#define f2(i,n,m) for(int i=n;i>=m;++i)
using namespace std;
template <typename T>
void read(T &x){
int w=1;x=0;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
x*=w;
}
int n,m,tot;
int to[N*N],from[N*N],deg[N];
double f[N][N],a[N*N];
vector<int>g[N];
bool cmp(double x,double y){return x>y;}
void gauss(int n){
int mx;double tmp;
f1(i,1,n){
mx=i;
f1(j,i+1,n+1)if(fabs(f[j][i])>fabs(f[mx][i]))mx=j;
swap(f[i],f[mx]);
f1(j,1,n)if(i!=j){
tmp=f[j][i]/f[i][i];
f1(k,i,n+1)f[j][k]-=tmp*f[i][k];
}
}
}
void work(){
double ans=0;
f[1][n]=-1;//初始化第n个点为常数
f1(i,1,n-1){
f[i][i]=-1.0;
for(auto j:g[i])if(j!=n)
f[i][j]=1.0/deg[j];
}
gauss(n-1);//因为第n个点为终点，其他点无法从n点到达，所以其实只有n-1个未知数
f1(i,1,m){
if(from[i]!=n)a[i]+=f[from[i]][n]/f[from[i]][from[i]]*1.0/deg[from[i]];//这里因为上面的高斯消元没有除系数，所以要手动除，至于为啥不在上面除，因为结果会不一样，可以自己想想为啥。
if(to[i]!=n)a[i]+=f[to[i]][n]/f[to[i]][to[i]]*1.0/deg[to[i]];
}
sort(a+1,a+1+m,cmp);
f1(i,1,m)ans+=(a[i]*1.0*i);
printf("%.3Lf\n",ans);
}
void init(){
int x,y;
read(n),read(m);
f1(i,1,m){
read(x),read(y);
g[x].push_back(y);
g[y].push_back(x);
deg[x]++,deg[y]++;
from[++tot]=x,to[tot]=y;
}
}
signed main(){
init();
work();
return 0;
}
to be continue \(\dots\)
标签：f1,系数,详解,权值,mx,高斯消,deg From： https://www.cnblogs.com/windf/p/16724634.html