URAL1041[Nikifor]

恩，可以看一下LRJ黑书讲贪心那部分，在讲矩阵胚时有提到。
CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-24

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      typedef long long int Type;

      int M,N;

      vector<vector<Type> > v;

      vector<pair<int,int> > p;

      static Type abs(Type n)

      {

             return n>=0?n:-n;

      }

      static Type gcd(Type a,Type b)

      {

             return b?gcd(b,a%b):a;

      }     

      bool push(vector<vector<Type> >& get,vector<Type> add)

      {

           vector<int> first(N);

           for (int i=0;i<get.size();i++)

               for (int j=0;j<N;j++)

                   if (get[i][j]!=0)

                   {

                      first[i]=j;

                      break;

                   }

           for (int i=0;i<get.size();i++)

           {

               static const Type BIGPRIME=549979;

               Type _gcd=gcd(abs(add[first[i]]),abs(get[i][first[i]]));

               //assert(_gcd!=0);

               if (_gcd)

               {

               Type mulj=get[i][first[i]]/_gcd;

               Type mulget=add[first[i]]/_gcd;

               for (int j=0;j<N;j++)

                   add[j]=(add[j]*mulj-get[i][j]*mulget)%BIGPRIME;

               }

               bool can=false;

               for (int j=0;j<N;j++)

                   if (add[j]!=0) can=true;

               if (!can) return false;

           }

           get.push_back(add);

           return true;

      }

      public:

      Application()

      {

                    cin>>M>>N;

                    v.resize(M,vector<Type>(N));

                    for (int i=0;i<M;i++)

                        for (int j=0;j<N;j++)

                            cin>>v[i][j];

                    p.resize(M);

                    for (int i=0;i<M;i++)

                    {

                        cin>>p[i].first;

                        p[i].second=i;

                    }

      }

      int run()

      {

          sort(p.begin(),p.end());

          int total=0;

          vector<int> answer;

          vector<vector<Type> > get;

          for (int i=0;i<M;i++)

          {

              if (push(get,v[p[i].second]))

              {

                 total+=p[i].first;

                 answer.push_back(p[i].second);

              }

              if (get.size()==N) break;

          }

          if (get.size()==N)

          {

             cout<<total<<endl;

             sort(answer.begin(),answer.end());

             for (int i=0;i<answer.size();i++)

                 cout<<answer[i]+1<<endl;

          }

          else cout<<0<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}