P2455 [SDOI2006]线性方程组

题目

题目

思路

其实这题和之前的高斯消元差不多,但是,高斯-约旦消元法会导致一个问题:消元的顺序决定结果!
比如说前面有一组方程要求的项为0,我们需要把它与下面交换,但是如果没得换了,这时我们要把它们留到最后,因为它们决定我们是无解还是无唯一解,其实这个时候我们把它们随便代入一组方程即可,详见代码
code:

#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;
int n,l=1,tot,id[111],p[111];
struct f{
	double a[111];
} a[111];
double x,y;
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) for (int j=1;j<=n+1;j++) cin>>a[i].a[j];
	for (int j=1;j<=n;j++)
	{
		int t=l,mx=l;
		while (t<=n)
		{
		    if (a[t].a[j]>a[j].a[j]) mx=t;
		    t++;
		}
		swap(a[mx],a[l]);
		if (a[l].a[j]==0)
		{
			continue;
		}
		for (int i=1;i<=n;i++)
		{
			if (i==l) continue;
			x=a[i].a[j]/a[l].a[j];
			for (int k=1;k<=n+1;k++) a[i].a[k]-=a[l].a[k]*x;
		}
		id[j]=l,l++;
	}
	for (int i=1;i<=n;i++) if (id[i]==0) p[tot++]=i;
	int f=0;
	while (l<=n)
	{
		id[p[f]]=l;
		l++;
		f++;
	}
	for (int j=1;j<=n;j++)
	{
		if (!a[id[j]].a[j]&&a[id[j]].a[n+1])
		{
			cout<<"-1";
			return 0;
		}
	}
	for (int j=1;j<=n;j++)
	{
		if (!a[id[j]].a[j]&&!a[id[j]].a[n+1])
		{
			cout<<"0";
			return 0;
		}
	}
	for (int j=1;j<=n;j++)
	{
		printf("x%d=%.2lf\n",j,a[id[j]].a[n+1]/a[id[j]].a[j]);
	}
    return 0;
}

大年初一发题解,我也是疯了

上一篇:2021年度训练联盟热身训练赛第三场 L——Traveling Merchant(2*7线段树+查询时的区间合并)


下一篇:洛谷 P4929 【模板】舞蹈链(DLX)