VIJOS1052

URAL1041要用到高斯消元,所以找了这道VIJOS上的纯粹的高斯消元来练习。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-23


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;


template<typename Type>


class Function


{


      int n;


      vector<vector<Type> > matrix;


      vector<Type> answer;


      static Type abs(Type a)


      {


             return a>=0?a:-a;


      }


      void smaller(int step)


      {


           for (int i=step+1;i<n;i++)


               if (abs(matrix[i][step])>abs(matrix[step][step]))


                  matrix[step].swap(matrix[i]);


           for (int i=step+1;i<n;i++)


           {


               Type mul=matrix[i][step];


               Type div=matrix[step][step];


               for (int j=step;j<=n;j++)


                   matrix[i][j]-=matrix[step][j]*mul/div;


           }


      }


      void back(int step)


      {


           if (step==n-1)


              answer[step]=matrix[step][n]/matrix[step][step];


           else


           {


               answer[step]=matrix[step][n];


               for (int i=step+1;i<n;i++)


                   answer[step]-=matrix[step][i]*answer[i];


               answer[step]/=matrix[step][step];


           }


      }


      public:


      bool read()


      {


           cin>>n;


           matrix.resize(n,vector<Type>(n+1));


           answer.resize(n);


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


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


                   cin>>matrix[i][j];


           return true;


      }


      void solve()


      {


           for (int i=0;i<n-1;i++) smaller(i);


           for (int i=n-1;i>=0;i–) back(i);


      }


      template<typename Print_Type>


      void print()


      {


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


               cout<<Print_Type(answer[i])<<char((i+1==n)?’\n’:’ ‘);


      }


};


struct Integer


{


       long long int data;


       Integer(double get)


                      :data((long long int)(get+0.5))


       {


       }


       operator long long int()


       {


                return data;


       }


};


class Application


{


      public:


      Application()


      {


      }


      int run()


      {


          Function<double> f;


          f.read();


          f.solve();


          f.print<Integer>();


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}