改了一上午了,难死孩子了QWQ
  • 板块P5027 Barracuda
  • 楼主Durancer
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/1/16 11:55
  • 上次更新2023/11/5 04:47:04
查看原帖
改了一上午了,难死孩子了QWQ
230804
Durancer楼主2021/1/16 11:55

求dalao 帮忙看看,WA了一个点QWQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;
const int N=1e2+9;
int a[N][N];
int b[N][N];
int n,m;
int ans=0;
int idx=0;
int lim=0;
bool hang[N];//记录行是不是合法方案 
int cun[N][N];//表示第i个出错时j的值 
int tong[N*10000]; 
int cnt;
bool check()//存入每一个解 
{
	memset(tong,0,sizeof(tong));//清空 
	int maxn=0;
	for(int i=1;i<=n;i++)
	{
		if(!b[i][i])
		cun[lim][i]=0,hang[lim]=true;
		else if(b[i][i]&&!b[i][n+1])
		cun[lim][i]=0,hang[lim]=true;
		else if(b[i][n+1]/b[i][i]<=0)
		cun[lim][i]=0,hang[lim]=true;
		else 
		{
			cun[lim][i]=b[i][n+1]/b[i][i];	
			tong[cun[lim][i]]++;
			maxn=max(maxn,cun[lim][i]);
		}
	}
	if(tong[maxn]>1) hang[lim]=true;
	if(hang[lim]==true) cnt++;//如果不合法,就记录不合法的方案数 
}
void search()
{
	for(int i=1;i<=n+1;i++)
		swap(b[lim][i],b[n+1][i]);//将没有用的一行换到最下面 
	for(int i=1;i<=n;i++)
	{
		int maxn=i;
		for(int j=i+1;j<=n;j++)
			if(b[j][i]>b[maxn][i])
				maxn=j;
		for(int j=1;j<=n+1;j++)
			swap(b[i][j],b[maxn][j]);
		if(!b[i][i]) continue;
		for(int j=1;j<=n;j++)
		{
			if(j==i) continue;//别忘了判断i,i 
			int tmp=b[j][i]/b[i][i];
			for(int k=i+1;k<=n+1;k++)
				b[j][k]-=b[i][k]*tmp;
		} 
	}
//	cout<<lim<<endl;
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=n+1;j++)
//			cout<<b[i][j]<<" ";	
//		cout<<endl;
//	}
//	cout<<endl;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n+1;i++)
	{
		scanf("%d",&m);
		for(int j=1;j<=m;j++)
		{
			int x;
			scanf("%d",&x);
			a[i][x]++; 
		} 
		scanf("%d",&a[i][n+1]);
	}//按照方程组的方式输入
	for(int i=1;i<=n+1;i++)//枚举所有的情况 
	{
		memcpy(b,a,sizeof(a));
		lim=i;
		search();//计算 
		check(); 
	}
//	for(int i=1;i<=n+1;i++)
//	{
//		for(int j=1;j<=n;j++)
//		cout<<cun[i][j]<<" ";
//		cout<<endl;
//	}
	if(cnt!=n) 
	{
		cout<<"illegal"<<endl;
		return 0;
	}
	for(int i=1;i<=n+1;i++)
	{
		if(hang[i]) continue;//找出唯一和法的一行来  
		for(int j=1;j<=n;j++)
		{
			if(cun[i][j]>ans)
			{
				ans=cun[i][j];
				idx=j;
			} 
		}
	}
	cout<<idx<<endl;
	return 0;
} 
2021/1/16 11:55
加载中...