Skip to content

高斯消元

解法一

按1\~n的顺序选择未知数\(x_i\),选择\(x_i\)系数最大的方程，将选中的方程的\(x_i\)系数化为1，并用那个方程消去其他方程中的\(x_i\)项。

最后剩下一个只有一个未知数并且系数为1的方程，直接得出答案，用那个答案回带到其他方程，依次求解。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=110;
const double eps=1e-7;
double f[N][N];
double ans[N];
int n;
double abs1(double a){
    return a>=0.0?a:-a;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n+1;++j){
            scanf("%lf",&f[i][j]);
        }
    }
    for(int i=1;i<=n;++i){
        int r=i;
        for(int j=i;j<=n;++j){
            if(abs1(f[r][i])<abs1(f[j][i]))r=j;
        }

        if(abs1(f[r][i])<eps){//就是等于0，那就是说这个未知数所有方程系数都是0，肯定无解。
            printf("No Solution");
            return 0;
        }
        if(i!=r)swap(f[r],f[i]);
        double tmp=f[i][i];
        for(int j=i;j<=n+1;++j)f[i][j]/=tmp;
        for(int j=i+1;j<=n;++j){
            double tmp=f[j][i];
            for(int k=i;k<=n+1;++k){
                f[j][k]-=f[i][k]*tmp;
            }
        }
    }
    ans[n]=f[n][n+1];
    for(int i=n-1;i>=1;--i){
        for(int j=i+1;j<=n;++j){
            f[i][n+1]-=ans[j]*f[i][j];
        }
        ans[i]=f[i][n+1];
    }
    for(int i=1;i<=n;++i){
        printf("%.2lf\n",ans[i]);
    }
    return 0;
}

解法二

因为回带的过程复杂并且没有必要，所以我们直接不回带了。

每次只需要将除了选中的方程的其他所有方程的当前未知数都消除掉，那么最后就剩下n个只有一个未知数且系数为1的方程，直接输出答案即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=110;
double f[N][N];
int n;
double abs1(double a){
    return a>=0.0?a:-a;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n+1;++j)scanf("%lf",&f[i][j]);
    for(int i=1;i<=n;++i){
        int r=i;
        for(int j=i;j<=n;++j){
            if(abs1(f[r][i])<abs1(f[j][i]))r=j;
        }
        if(!abs1(f[r][i])){
            printf("No Solution");
            return 0;
        }
        if(i!=r)swap(f[r],f[i]);
        double tmp=f[i][i];
        for(int j=i;j<=n+1;++j)f[i][j]/=tmp;
        for(int j=1;j<=n;++j){
            if(j==i)continue;
            double tmp=f[j][i];
            for(int k=i;k<=n+1;++k)f[j][k]-=f[i][k]*tmp;//k=1也行，没必要
        }
    }
    for(int i=1;i<=n;++i){
        printf("%.2lf\n",f[i][n+1]);
    }
    return 0;
}

P3389 模板

P2011

对于每个不是正极或负极的点\(u\)，都有：

\[\sum_{v_i}\frac{U_{v_i}-U_u}{R_{w_i}}=0\]

将所有是正极负极的点的结果移到\(n+1\)表示常数，而\(v_i\)得系数为\(-\frac{1}{R_{w_i}}\),\(u\)得系数为\(\sum _{v_i}\frac{1}{R_{w_i}}\)

那么会有n-k个式子，一共n-k个未知数，对应求解即可。

注意写法中，每个式子中会有0系数存在，要忽略这些0系数，并且未知数编号要与列号一一对应。(vis[i]数组的作用)

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
const int N=440,M=2e5+10;
double f[N][N],ans[N];
int head[N],vis[N],id[N];
int cnt,n,m,k,q,tot;
struct node{
    int v,nxt;
    double w;
}e[M<<1];
double abs1(double a){
    return a>=0.0?a:-a;
}
void add(int u,int v,double w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
    return;
}
void clear1(){
    for(int i=0;i<=n;++i)ans[i]=-1.0;
    ans[0]=0.0;
}
void init(){
    tot=0;
    for(int u=0;u<=n;++u){
        if(ans[u]<0.0){
            tot++;
            vis[tot]=u;

            for(int i=head[u];~i;i=e[i].nxt){
                int v=e[i].v;
                double w=e[i].w;
                if(ans[v]>=0.0){
                    f[tot][n+1]+=ans[v]/w;//constant 
                }else f[tot][v]-=1.0/w;
                f[tot][u]+=1.0/w;
            }
        }
    }
}
void work(){
    for(int u=1,i;u<=tot;++u){
        i=vis[u];
        int r=u;
        for(int j=u;j<=tot;++j){
            if(abs1(f[r][i])<abs1(f[j][i]))r=j;
        }
        /*if(!abs1(f[r][i])){
            return 0;
        }*/
        if(u!=r)swap(f[r],f[u]);
        double tmp=f[u][i];
        for(int j=i;j<=n+1;++j)f[u][j]/=tmp;
        for(int j=u+1;j<=tot;++j){
            double tmp=f[j][i];
            for(int k=i;k<=n+1;++k){
                f[j][k]-=f[u][k]*tmp;
            }
        }
    }

    ans[vis[tot]]=f[tot][n+1];
    for(int i=tot-1;i>=1;--i){
        for(int j=i+1;j<=n;++j){
            f[i][n+1]-=f[i][vis[j]]*ans[vis[j]];
        }
        ans[vis[i]]=f[i][n+1];
    }
}
signed main(){
    memset(head,-1,sizeof head);
    cnt=-1;

    scanf("%lld%lld%lld%lld",&n,&m,&k,&q);

    clear1();

    for(int i=1,tmp;i<=k;++i){
        scanf("%lld",&tmp);
        scanf("%lf",&ans[tmp]);
    }

    for(int i=1,u,v,w;i<=m;++i){
        scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }

    init();
    work();

    for(int i=1,x,y;i<=q;++i){
        scanf("%lld%lld",&x,&y);
        printf("%.2lf\n",ans[x]-ans[y]);
    }


    return 0;
}
/*
3 5 1 3
2 18
2 1 6
2 3 2
1 3 6
3 0 6
1 0 2
2 0
1 3
2 1
*/