2344.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"
#include"algorithm"
#include"math.h"

using namespace std;

int n,m;
const double eps=1e-8;
const int size=2000;

double a[size][size];
bool sign[size];

void swap_c(int k,int l)
{
	int i;
	for(i=0;i<m;i++)
		std::swap(a[i][k],a[i][l]);
}

bool guass()
{
	int i,j,k,l;double temp;
	for(i=0;i<m;i++)
		sign[i]=1;
	
	for(l=0,i=0;i<n;i++)
	{
		while(fabs(a[l][i])<eps)
		{
			for(j=i+1;j<n;j++)
				if(fabs(a[l][j])>eps)
				{
					swap_c(i,j);
					break;
				}
			
			if(j==n)
			{
				sign[l]=0;
				l++;
			}
			if(l>=m)
				return 0;
		}
		for(k=l+1;k<m;k++)
		if(fabs(a[k][i])>eps)
		{
			temp=a[k][i]/a[l][i];
			for(j=i;j<n;j++)
				a[k][j]-=a[l][j]*temp;
		}
		l++;
	}
	return 1;
}
int value[size];
int id[size];
int b[size][size];
int flag[size];

bool cmp(int a,int b)
{
	return value[a]<value[b];
}

int main()
{
	int i,j;
	scanf("%d %d",&m,&n);
	for(i=0;i<m;i++)
	for(j=0;j<n;j++)
		scanf("%d",&b[i][j]);
	for(i=0;i<m;i++)
	{
		scanf("%d",&value[i]);
		value[i]=value[i]*10000+i;
	}

	for(i=0;i<m;i++)
		id[i]=i;

	sort(id,id+m,cmp);

	for(i=0;i<m;i++)
	for(j=0;j<n;j++)
		a[i][j]=b[id[i]][j];
	
	if(!guass())
		printf("0\n");
	else
	{
		int ans=0;
		for(i=0;i<m;i++)
			flag[i]=0;

		for(i=0,j=0;i<m&&j<n;i++)
			if(sign[i])
			{
				j++;
				ans+=value[id[i]]/10000;
				flag[id[i]]=1;
			}
		printf("%d\n",ans);
		for(i=0,j=0;i<m&&j<n;i++)
			if(flag[i])
			{
				printf("%d\n",i+1);
				j++;
			}
	}
	return 0;
}