题解 P3389 【【模板】高斯消元法】

机智的岂凡 · 2017-10-21 10:12:11 · 题解

既然大家都真的都用高斯消元，那我就来一发带入的吧

例如 2x1+3x2+x3=4

可以化为

x1=(4-3x2-x3)/2=0x1-1.5x2-0.5x3+2

再把x1带入其它式子

最后解出axn=b

然后除一下·

再把这个·再带一遍，解xn-1

速度：O（n^4）

附上代码

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#define main_ret (573+44805-9872^23*98237+~3423)*0
using namespace std;
const double feidiao=3221314;
double ans[105];
double ans2[105];
double gaoxiang[105][105]; 
double gaoxiang2[105][105];
double tihuan[105];//xishuj
double real_ans[105];
int biggest;
int n;
void dr(int a,int x)
{
    double q[105];
    for(int i=0;i<n;i++) q[i]=gaoxiang[a][i];
    if(q[x]==0)
    return;
    for(int i=0;i<n;i++)
    {
        if(i==x) continue;
        tihuan[i]=-q[i]/q[x];
    }
    double t=ans[a]/q[x];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(j==x) continue;
            gaoxiang[i][j]+=gaoxiang[i][x]*tihuan[j];
        }
        ans[i]-=t*gaoxiang[i][x];
        gaoxiang[i][x]=0;
    }
    return;
}
void work()
{
    for(int tt=1;tt<=n;tt++)
    {
        for(int i=0;i<n-tt;i++) 
        {
            dr(i,i);
        }
        if(gaoxiang[n-tt][n-tt]==0) {cout<<"No Solution"<<endl;exit(0);}
        real_ans[n-tt]=ans[n-tt]/gaoxiang[n-tt][n-tt];
        for(int i=0;i<n;i++)
        {
            ans2[i]-=real_ans[n-tt]*gaoxiang2[i][n-tt];
            gaoxiang2[i][n-tt]=0;
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                gaoxiang[i][j]=gaoxiang2[i][j];
            }
            ans[i]=ans2[i];
        }
    }
    return;
}
void input()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>gaoxiang[i][j];
            gaoxiang2[i][j]=gaoxiang[i][j];
        }
        cin>>ans[i];
        ans2[i]=ans[i];
    }
    return;
}
void output()
{
    for(int i=0;i<n;i++)
    {
        printf("%.2lf\n",real_ans[i]);
    }
}
int main()
{
    input();
    work();
    output();
    //system("pause");
    return main_ret;
         for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cout<<gaoxiang[i][j]<<" ";
            }
            cout<<ans[i]<<endl;
        }
       system("pause");
}

/*

x+kc=y(mod L)
d=-kc(mod L)
d=(l-k)c mod L
l-k=d/c

*/ 400ms龟速AC…