高斯消元

高斯消元基本原理

模拟國小生解多元一次方程（誰家國小生解50元一次方程啊！！！）

算法步驟

首先，将方程弄成一個矩陣。

例如這個方程：

⎧⎩⎨⎪⎪2x+y−z=2x+2y−z=5x−y+2z=−7⎫⎭⎬⎪⎪

就弄成這樣一個矩陣：

⎡⎣⎢21112−1−1−1225−7⎤⎦⎥

然後就開始高斯消元了 qwq

首先，我們枚舉目前要消元的列k，那麼除了第k個方程的列k以外的其他方程的列k都要被消元掉（當然也可以被消成倒三角形，這個等下再講）

我們k行及以後的所有行，找到k列絕對值最大的那一行與第k行交換以減少誤差和防止無解。

在實數消元的時候，我們可以将第k行全部除以一個a[k][k]，這樣第k個元素就是1了，友善于後面的運算。

然後再将除了第k行以外的每一行i的每一個元素a[i][j]都減去一個a[i][k]*a[k][j]，這樣就消去了這一行的元素k，弄完了後，第一行就隻有第一個常數不為0了，以此類推，可以獲得解。

不過如果是整數消元的話這樣還是不行。

同樣将k行換成第k列絕對值最大的那一行後，用公倍數消元（注意加還是減），使得得到一個”倒三角“

⎡⎣⎢200130−1−1428−8⎤⎦⎥

然後 4z=−8,z=−2

3y−z=8y=(8+z)/3 ,得到 y=2

2x+y−z=2 解出 x=−1

例題及代碼

洛谷P3389

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
double a[][];
int n;
bool gauss(){
    int k,i,j,bj;double t;
    for(k=;k<n;k++){
        bj=k;
        for(i=k+;i<n;i++)
            if(fabs(a[i][k])>fabs(a[bj][k]))bj=i;
        if(fabs(a[bj][k])<)return ;
        for(j=k;j<=n;j++)swap(a[bj][j],a[k][j]);
        t=a[k][k];
        for(j=k;j<=n;j++)a[k][j]/=t*;
        for(i=;i<n;i++)if(k!=i){//notice:if
            t=a[i][k];
            for(j=k;j<=n;j++)a[i][j]-=a[k][j]*t*;
        }
    }
    return ;
}
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=;i<n;i++)
        for(j=;j<n+;j++)scanf("%lf",&a[i][j]);
    if(gauss())for(i=;i<n;i++)printf("%.2lf\n",a[i][n]);
    else printf("No Solution");
    return ;
}
           

洛谷P2962

由于異或有交換率，是以異或方程也可以用高斯消元來解qwq

就是構造異或方程然後解啦啦

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read(){
    int q=;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*+ch-'0',ch=getchar();
    return q;
}
int n,m,ans=INT_MAX;
int a[][],x[];
void gauss(){
    int i,j,bj,k;
    for(k=;k<=n;k++){
        bj=k;
        for(i=k+;i<=n;i++)if(a[i][k]){bj=i;break;}
        if(bj!=k)for(j=;j<=n+;j++)swap(a[bj][j],a[k][j]);
        for(i=k+;i<=n;i++)if(a[i][k]){
            for(j=;j<=n+;j++)a[i][j]^=a[k][j];
        }
    }
}
void dfs(int xx,int tot){
    if(tot>ans)return;
    if(!xx){ans=min(ans,tot);return;}
    if(a[xx][xx]){
        x[xx]=a[xx][n+];
        for(int j=n;j>xx;j--)x[xx]^=x[j]&a[xx][j];
        if(x[xx])dfs(xx-,tot+);
        else dfs(xx-,tot);
    }
    else {
        x[xx]=;dfs(xx-,tot);
        x[xx]=;dfs(xx-,tot+);
    }
}
int main()
{
    int i,j,xx,yy;
    n=read();m=read();
    for(i=;i<=m;i++){xx=read();yy=read();a[xx][yy]=a[yy][xx]=;}
    for(i=;i<=n;i++)a[i][n+]=,a[i][i]=;
    gauss();dfs(n,);printf("%d",ans);
    return ;
}
           

類似的題目：poj1222，洛谷P2247/codevs2311/bzoj1923（要用bitset卡常才能過）

期望與高斯消元

其實…..和普通高斯消元也差不多，就是列出期望方程然後解就可以了。

HDU4418

題目大意是有一個0,1,2…n-1,n,n-1…2,1,0這樣的環，走i步的機率是p[i]，求從起點走到終點的期望。

那麼我們可以列出方程：f[i]= ∑ (p[k]*(f[(i+k)%n]+k))

然後把方程變形，再高斯消元即可

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int T,tot,n,m,v,u,d;
int g[],q[];
double p[],a[][],eps=;
void bfs(){
    int i,he=,ta=,to;
    q[he]=u;g[u]=tot++;
    while(he<=ta){
        for(i=;i<=m;i++){
            if(fabs(p[i])<eps)continue;
            to=(q[he]+i)%n;
            if(g[to]==-){g[to]=tot++;q[++ta]=to;}
        }
        he++;
    }
}
bool guss(){
    int i,j,k,bj;double t;
    for(k=;k<tot;k++){
        bj=k;
        for(i=k+;i<tot;i++)
            if(fabs(a[i][k])>fabs(a[bj][k]))bj=i;
        if(fabs(a[bj][k])<eps)return ;
        if(bj!=k)for(j=k;j<=tot;j++)swap(a[k][j],a[bj][j]);
        t=a[k][k];
        for(j=k;j<=tot;j++)a[k][j]/=t;
        for(i=;i<tot;i++)if(i!=k){
            if(fabs(a[i][k])<eps)continue;
            t=a[i][k];
            for(j=k;j<=tot;j++)a[i][j]-=t*a[k][j];
        }
    }
    return ;
}
int main()
{
    int i,j;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d%d%d",&n,&m,&v,&u,&d);
        for(i=;i<=m;i++){scanf("%lf",&p[i]);p[i]/=;}
        if(u==v){printf("0.00\n");continue;}
        n=n*-;if(d==&&u!=)u=n-u;
        for(i=;i<n;i++)g[i]=-;
        tot=;bfs();
        if(g[v]==-&&g[n-v]==-){printf("Impossible !\n");continue;}
        memset(a,,sizeof(a));
        for(i=;i<n;i++){
            if(g[i]==-)continue;
            a[g[i]][g[i]]=;
            if(i==v||i==n-v)continue;
            for(j=;j<=m;j++){
                if(fabs(p[j])<eps)continue;
                int to=(i+j)%n;
                if(g[to]==-)continue;
                a[g[i]][g[to]]-=p[j];a[g[i]][tot]+=p[j]*j;
            }
        }
        if(!guss()){printf("Impossible !\n");continue;}
        printf("%.2lf\n",a[g[u]][tot]);
    }
    return ;
}
           

類似的題目：HDU2262

洛谷P3232（即bzoj3143） 題解戳這