1041.cpp

我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2~3个比较难的是MAIGO的程序

//linearDep  using Greedy
#include <iostream>
#include <algorithm>
using namespace std;

const int maxN = 2000;
const int maxM = 2000;
const int PRIME = 17863;
int vecArr[maxN + 1][maxM + 1];
int a[maxN + 1][maxN + 1];  // temp matrix
int ord[maxN + 1], price[maxN + 1];
int n,m;
bool isLinearDep(int w, int h)  // linearDependance;
{
   int i, j, k, tk, i2;
   int t[maxN + 1]; 
   for( k = 1, tk = 1; k <= h; k++, tk++ )
   {
      for( i2 = tk; i2 <= w; i2++ ){
        for( i = k; i <= h; i++ )
           if(a[i][i2] != 0)
           {
               memcpy(t, a[k], sizeof(t));
               memcpy(a[k], a[i],sizeof(a[k]));
               memcpy(a[i], t, sizeof(a[i]));
               break;
           }
        if( i <= h )break;
      }
      
      if( i2 > w )  return false;
      tk = i2;
      
      for( i = k + 1; i <= h ; i++ )
      {
         int temp = a[i][tk];
         for( j = tk; j <= w; j++ )
            {
               a[i][j] = (a[i][j]*a[k][tk])%PRIME;
               a[i][j] -= (temp * a[k][j])%PRIME;
            }
      }
   }
   for( i = 1; i <= w; i++ )if( a[h][i] !=0 ) return true;
   return false;
}

void readIn()
{
   int i , j;
   cin >> m >> n;
   for( i = 1; i <= m; i++ )
      for( j = 1; j <= n; j++ )
         cin >> vecArr[i][j];
   for( i = 1; i <= m; i++ )
      {cin >> price[i]; ord[i] = i;}
}
bool cmp(const int& a, const int& b){ return price[a] < price[b]; }
void work()
{
   int i, tot = 0, totPrice = 0;
   int ans[maxN + 1];
   
   stable_sort(ord + 1, ord + m + 1, cmp);
   
   for( i = 1; i <= m; i++ )
   {
      tot++;
      memcpy( a[tot], vecArr[ ord[i] ],sizeof(a[tot]) );
      if( isLinearDep( n , tot ) ){ totPrice += price[ ord[i] ]; ans[tot] = ord[i];}
      else
      {
         memset(a[tot], 0, sizeof(a[tot]));
         tot --;
      }
      
      if( tot == n ) break; 
   }
   if( tot == n )
   {
      cout << totPrice << endl;
      sort(ans+1, ans + n + 1);
      for( i = 1; i <= n; i++ )
         cout << ans[i] << endl;
   }
   else cout << 0 << endl;
}

int main()
{
   freopen("1041.in","r",stdin);
   freopen("1041.out","w",stdout);
   readIn();
   work();
   return 0;
}