Poj Solution 2344

http://poj.org/problem?id=2344

#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("0n");
    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("%dn",ans);
        for(i=0,j=0;i<m&&j<n;i++)
            if(flag[i])
            {
                printf("%dn",i+1);
                j++;
            }
    }
    return 0;
}