一个玄学
查看原帖
一个玄学
180924
FLAT_LCH楼主2022/11/22 22:30

这道题我用高斯消元过了,约旦消元挂了 但是理论上约旦消元精度更高啊???? 附上代码,两种消元都有

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int n,m,k,q;
bool zheng[300]={};
int u[300];
double a[300][300]={};

void readd()
{
	cin>>n>>m>>k>>q;
	zheng[0]=true;a[0][0]=1;
	for(int i=1,x,y;i<=k;i++)
	{
		cin>>x>>y;
		zheng[x]=true;
		a[x][x]=1;
		a[x][n+1]=y;
	}
	
	for(int i=1,x,y,z;i<=m;i++)
	{
		cin>>x>>y>>z;
		if(!zheng[x])
		{
			a[x][y]+=1.0/z;
			a[x][x]-=1.0/z;
		}
		if(!zheng[y])
		{
			a[y][x]+=1.0/z;
			a[y][y]-=1.0/z;
		}
	}
	
	for(int i=0;i<=n;i++)
	{
		if(abs(a[i][i])<1e-10)
			a[i][i]=1;
	}
}

inline void pt()
{
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n+1;j++)
			cout<<a[i][j]<<' ';
		cout<<endl;
	}
	cout<<"-------\n\n";
}

inline void ydxy()
{
	for(int i=0;i<=n;i++)
	{
		u[i]=0;
		for(int j=1;j<=n;j++)
			if(abs(a[j][i])>abs(a[u[i]][i]))u[i]=j;
		
		for(int j=0;j<=n+1;j++)
		{
			if(i==j)continue;
			a[u[i]][j]/=a[u[i]][i];
		}
		a[u[i]][i]=1;
			
		for(int j=0;j<=n;j++)
		{
			if(j==u[i])continue;
			double t=a[j][i];
			//cout<<"t="<<t<<endl;
			for(int k=0;k<=n+1;k++)
				a[j][k]-=a[u[i]][k]*t;
		}
		
		//cout<<i<<' '<<u[i]<<"@@@\n";
		//pt();
	}
}

inline void gsxy()
{
	for(int i=0;i<=n;i++)
	{
		u[i]=i;
		
		for(int j=0;j<=n+1;j++)
		{
			if(i==j)continue;
			a[u[i]][j]/=a[u[i]][i];
		}
		a[u[i]][i]=1;
			
		for(int j=0;j<=n;j++)
		{
			if(j==u[i])continue;
			double t=a[j][i];
			//cout<<"t="<<t<<endl;
			for(int k=0;k<=n+1;k++)
				a[j][k]-=a[u[i]][k]*t;
		}
		
		//cout<<i<<' '<<u[i]<<"@@@\n";
		//pt();
	}
}

void print()
{
	//pt();
	
	for(int i=1,x,y;i<=q;i++)
	{
		cin>>x>>y;
		printf("%.2lf\n",a[u[x]][n+1]-a[u[y]][n+1]);
	}
}
int main()
{
	readd();
	//pt();
	//cout<<"!!!\n";
	//ydxy();
	gsxy();
	print();
	
	return 0;
}
2022/11/22 22:30
加载中...