凌晨被卡了,求大佬改错T^T
查看原帖
凌晨被卡了,求大佬改错T^T
266988
Wjh2468899楼主2021/2/2 02:10

5,8,9 wa了。。

#include<iostream>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
map<double,int> mn; //用于记录三角形重量出现的次数 
const long double eps=1e-14;
const int maxn=105;
double mp[maxn][maxn],cpy[maxn][maxn],ans[maxn]; 
//mp是读入,cpy是删掉一行后的mp,ans是三角形重量; 
int n,res,ori;
//n是矩阵大小,res是方案个数,ori是答案; 
bool check(double s){
	//判断三角形重量是否合法 
	++mn[s];
	if(int(s)==s&&s>0&&mn[s]==1) return true;
	return false;
}
void gauss(){
	mn.clear();//清空map 
	//22-48行 gauss板子 
	for(int i=1;i<=n;++i){
		int r=i;
		for(int j=i+1;j<=n;++j){
			if(fabs(cpy[r][i])<fabs(cpy[j][i])) r=j;
		}	
		if(fabs(cpy[r][i])<eps){
			return;
		}
		if(i!=r) swap(cpy[r],cpy[i]);
		double div=cpy[i][i];
		for(int j=i;j<=n+1;++j){
			cpy[i][j]/=div;
		}
		for(int j=i+1;j<=n;++j){
			div=cpy[j][i];
			for(int k=i;k<=n+1;++k){
				cpy[j][k]-=div*cpy[i][k];
			}
		}
	}
	ans[n]=cpy[n][n+1];
	for(int i=n-1;i>=1;--i){
		ans[i]=cpy[i][n+1];
		for(int j=n;j>i;--j){
			ans[i]-=ans[j]*cpy[i][j];
		}
	}
	//判断是否合理 
	for(int i=1;i<=n;++i)
		if(!check(ans[i])) return;
	//如果合理找到编号 
	int mx=0;
	res++;//方案数 ++ 
	for(int i=1;i<=n;++i){
		if(ans[i]>mx) mx=ans[i],ori=i;
	} 
}
int main(){
	cin>>n;
	//读入mp 
	for(int i=1;i<=n+1;++i){
		int m; cin>>m;
		for(int j=1;j<=m;++j){
			int tmp; cin>>tmp;
			mp[i][tmp]++;
		}
		cin>>mp[i][n+1];
	}
	//删行处理 
	for(int i=1;i<=n+1;++i){
		for(int j=1,cnt=1;j<=n+1;++j){
			if(j==i) continue;
			for(int k=1;k<=n+1;++k){
				cpy[cnt][k]=mp[j][k];
			}
			cnt++;
		}
		gauss();
	}
	if(res!=1) cout<<"illegal";
	else cout<<ori;
	return 0;
}
2021/2/2 02:10
加载中...