20pts 高斯消元求助
查看原帖
20pts 高斯消元求助
541069
SuperCowHorse楼主2023/6/16 20:03

甚至还有一个 WA 的,我是蒟蒻呜呜呜

#include<bits/stdc++.h>
using namespace std;

//----------Set----------

//Define.
#define pb push_back
#define mp make_pair
#define fi first
#define se second

//Typedef.
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef map<int,int> mii;
typedef map<int,bool> mib;
typedef map<string,int> msi;
typedef map<string,bool> msb;
typedef map<pii,pii> mpp;

//Const.
const int maxn=105;
const int maxm=1e5+5;
const ll inf=0x3f3f3f3f;
const int mod=998244353;
const ld eps=1e-6;
const ld dl=0.9969;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};

//----------Finished----------
int n,a[maxn][maxn],w[maxn];
ld c[maxn][maxn],g[maxn],x[maxn];
inline bool Gauss(int n){
	for(int i=1;i<=n;++i){
		for(int j=i+1;j<=n;++j){
			ld del=c[j][i]/c[i][i];
			for(int k=i;k<=n;++k){
				c[j][k]-=c[i][k]*del;
			}
			g[j]-=g[i]*del;
		}
	}
	for(int i=n;i>=1;--i){
		x[i]=g[i];
		for(int j=n;j>i;--j){
			x[i]-=x[j]*c[i][j];
		}
		if(c[i][i]==0){
			return 0;
		}
		x[i]/=c[i][i];
	}
	return 1;
}
int X[maxn];
bool fl;int ans;
inline void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n+1;++i){
		scanf("%d",&a[i][0]);
		for(int j=1;j<=a[i][0];++j){
			scanf("%d",&a[i][j]);
		}
		scanf("%d",&w[i]);
	}
	for(int p=1;p<=n+1;++p){
		int tot=0;
		memset(c,0,sizeof(c));
		for(int i=1;i<=n+1;++i){
			if(i==p) continue;
			++tot;
			for(int j=1;j<=a[i][0];++j){
				c[tot][a[i][j]]+=1.0;
			}
			g[tot]=ld(w[i]);
		}
		if(!Gauss(n)){
			continue;
		}
		//判断正整数
		bool o=0;
		for(int i=1;i<=n;++i){
			if(fabs(x[i]-ceil(x[i]))>eps||x[i]<0.0){
				o=1;
				break;
			}
		}
		if(o) continue;
		for(int i=1;i<=n;++i){
			X[i]=int(x[i]);
		}
		//判断最大值唯一
		int mx=-1,cnt=0,pos=-1;
		for(int i=1;i<=n;++i){
			if(X[i]>mx){
				mx=X[i];
				pos=i;
			}
		}
		for(int i=1;i<=n;++i){
			if(X[i]==mx){
				++cnt;
			}
		}
		if(cnt>1) continue;
		//判断是否有多组解,即可能有不同的方案可以构造唯一解
		if(fl){
			printf("illegal");
			return;
		}
		fl=1;ans=pos;
	}
	if(!fl){
		printf("illegal");
		return;
	}
	printf("%d",ans);
}

signed main(){
	int T=1;
	for(;T;--T) solve();
	return 0;
}
2023/6/16 20:03
加载中...