高斯-约旦 90pts WA #3
  • 板块P5027 Barracuda
  • 楼主_qingshu_
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/2/29 10:07
  • 上次更新2024/2/29 16:59:49
查看原帖
高斯-约旦 90pts WA #3
602803
_qingshu_楼主2024/2/29 10:07
#include<bits/stdc++.h>
using namespace std;
int n;
double mp[120][120],mp2[120][120],ans,res,eps=1e-7;
inline int gauss(){
	for(int i=1;i<=n;i++){
		int maxx=i;
		for(int j=i+1;j<=n;j++){
			if(fabs(mp2[maxx][i])<fabs(mp2[j][i])){
				maxx=j;
			}
		}
		if(fabs(mp2[maxx][i])<eps)return 0;
		swap(mp2[maxx],mp2[i]);
		for(int k=1;k<=n;k++){
			if(k==i)continue;
			double p=mp2[k][i]/mp2[i][i];
			for(int j=i;j<=n+1;j++)mp2[k][j]-=mp2[i][j]*p;
		}
	}
	return 1;
}
int main(){
	cin>>n;
	for(int i=1,x;i<=n+1;i++){
		cin>>x;
		for(int j=1,y;j<=x;j++){
			cin>>y;
			mp[i][y]=1;
		}
		cin>>x;
		mp[i][n+1]=x;
	}
	for(int flag=1;flag<=n+1;flag++){
		for(int i=1;i<=n+1;i++){
			for(int j=1;j<=n+1;j++){
				mp2[i][j]=mp[i][j];
			}
		}
		swap(mp2[flag],mp2[n+1]);
		if(gauss()){
			bool check=0;
			long long lans=ans,lres=res;ans=0;
			for(int i=1;i<=n;i++){
				if(mp2[i][i]==0||(mp2[i][n+1]/mp2[i][i])<=0){
					check=1;
					break;
				}
				if(mp2[i][n+1]/mp2[i][i]==ans)check=1;
				if(mp2[i][n+1]/mp2[i][i]>ans){
					check=0;
					ans=mp2[i][n+1]/mp2[i][i];
					res=i;
				}
			}
			if(check==1){
				ans=lans;res=lres;
				continue;
			}
			if(lans){
				cout<<"illegal"<<"\n";
				exit(0);
			}
		}
	}
	if(!res){
		cout<<"illegal"<<"\n";
		exit(0);
	}
	cout<<res<<endl;
} 
2024/2/29 10:07
加载中...