Stk 5 WA 求条 玄关

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#include <cstring>

#define eps 1e-9
using namespace std;
const int maxn=200;
double fA[maxn][maxn],fb[maxn],fc[maxn];
double A[maxn][maxn],b[maxn],c[maxn];
double v;
bool B[maxn],N[maxn];
int n,m;
bool fail=0;
//bool start;
//void ptx(bool x=1)
//{
//	printf("z=%f",v);
//	for(int i=x;i<=n+m;++i)
//	{
//		if(N[i])
//		{
//			printf("+%fx_%d",c[i],i);
//		}
//	}
//	printf("\n");
//	for(int i=x;i<=n+m;i++)
//	{
//		if(B[i])
//		{
//			printf("x_%d=%f",i,b[i]);
//			for(int j=x;j<=n+m;++j)
//			{
//				if(N[j])
//				{
//					printf("-%fx_%d",A[i][j],j);
//				}
//			}
//			printf("\n");
//		}
//	}
//	printf("\n");
//}
void PRINT_ANS()
{
	for(int i=1;i<=n+m;++i)
	{
		if(B[i]&&b[i]<0)
		throw"";
	}
	printf("%.10f\n",v);
	for(int i=1;i<n;++i)
	{
		if(B[i])
		{
			printf("%.10f ",b[i]);
		}
		else
		{
			printf("0.00000000 ");
		}
	}
	if(B[n])
	{
		printf("%.10f\n",b[n]);
	}
	else
	{
		printf("0.00000000\n");
	}
}
void PIVOT(int pin,int pout,bool x)
{
	for(int i=x;i<=n+m;++i)
	{
		A[pin][i]=A[pout][i]/A[pout][pin];
	}
	A[pin][pin]=0;
	A[pin][pout]=1/A[pout][pin];
	b[pin]=b[pout]/A[pout][pin];
	b[pout]=0;
	for(int i=x;i<=n+m;++i)
	{
		A[pout][i]=0;
	}
	B[pin]=1;
	N[pin]=0;
	B[pout]=0;
	N[pout]=1;
	for(int i=x;i<=n+m;++i)
	{
		if(i==pin||i==pout)continue;
		if(B[i])
		{
			for(int j=x;j<=n+m;++j)
			{
				if(j!=pin&&N[j])
				{
					A[i][j]-=A[i][pin]*A[pin][j];
				}
			}
			b[i]-=A[i][pin]*b[pin];
			A[i][pin]=0;
		}
	}
	for(int i=x;i<=n+m;++i)
	{
		if(N[i])
		{
			c[i]-=c[pin]*A[pin][i];
		}
		
	}
	v+=c[pin]*b[pin];
	c[pin]=0;
}
bool S(bool x)
{
	while(1)
	{
		int k=-1;
		double tth=eps;
		for(int i=x;i<=n+m;++i)
		{
			if(N[i]&&c[i]>tth)
			{
				k=i;
				break;
			}
		}
		if(k==-1)
		{
			return 1;
		}
		double th=1e18;
		int pout=-1;
		for(int i=x;i<=n+m;++i)
		{
			if(B[i])
			{
				if(A[i][k]>eps)
				{
					if(b[i]/A[i][k]<th)
					{
						th=b[i]/A[i][k];
						pout=i;
					}
				}
			}
		}
		if(pout==-1)
		{
			return 0;
		}
		PIVOT(k,pout,x);
		//ptx();
	}
}
bool INIT_S()
{
	double minr=-eps;
	int k=-1;
	for(int i=1;i<=m;++i)
	{
		if(fb[i]<minr)
		{
			minr=fb[i];
			k=i;
		}
	}
	for(int i=1;i<=m;++i)
	{
		for(int j=1;j<=n;++j)
		{
			A[i+n][j]=fA[i][j];
		}
		b[i+n]=fb[i];
		B[i+n]=1;
	}
	for(int i=1;i<=n;++i)
	{
		N[i]=1;
	}
	if(k==-1)
	{
		for(int i=1;i<=n;++i)
		{
			c[i]=fc[i];
		}	
		return 1;
	}
	c[0]=-1;
	for(int i=1;i<=m;++i)
	{
		A[i+n][0]=-1;
	}
	N[0]=1;
	//ptx(0);
	PIVOT(0,k+n,0);
	//printf("%d-%d\n",k+n,0);
	//ptx(0);
	S(0);
	if(abs(v)>eps)
	{
		return 0;
	}
	v=0;
	for(int i=0;i<=n+m;++i)
	{
		A[i][0]=c[i]=A[0][i]=0;
	}
	for(int i=1;i<=n;++i)
	{
		if(B[i])
		{
			for(int j=1;j<=n+m;++j)
			{
				c[j]-=fc[i]*A[i][j];
			}
			v+=fc[i]*b[i];
		}
		else
		{
			c[i]+=fc[i];
		}
	}
	N[0]=B[0]=0;
	return 1;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%lf",&fc[i]);
	}
	for(int i=1;i<=m;++i)
	{
		for(int j=1;j<=n;++j)
		{
			scanf("%lf",&fA[i][j]);
		}
		scanf("%lf",&fb[i]);
	}
	if(!INIT_S())
	{
		printf("Infeasible\n");
		return 0;
	}
//	start=1;
	//ptx();
	if(!S(1))
	{
		printf("Unbounded\n");
		return 0;
	}
	PRINT_ANS();
	return 0;
}