URAL1042[Central heating]

高斯消元。然后把xor当成加号和减号,把and当成乘号就行了。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-25


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


{


      int N;


      vector<vector<bool> > v;


      vector<bool> answer;


      public:


      Application()


      {


                    cin>>N;


                    v.resize(N,vector<bool>(N+1,false));


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


                    {


                        int get;


                        for (cin>>get;get!=-1;cin>>get)


                            v[get-1][i]=true;


                    }


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


                        v[i][N]=true;


      }


      int run()


      {


          bool nosolution=false;


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


          {


              for (int j=i+1;j<N;j++)


                  if (v[j][i]>v[i][i])


                     v[i].swap(v[j]);


              if (v[i][i]==false)


              {


                 nosolution=true;


                 break;


              }


              for (int j=i+1;j<N;j++)


              {


                  bool mulj=v[i][i];


                  bool muli=v[j][i];


                  for (int k=i;k<=N;k++)


                      v[j][k]=((v[j][k] and mulj) xor (v[i][k] and muli));


              }


          }


          answer.resize(N);


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


          {


              bool total=v[i][N];


              for (int j=i+1;j<N;j++)


                  total=total xor (answer[j] and v[i][j]);


              answer[i]=total and v[i][i];


          }


          if (nosolution) cout<<“No solution”<<endl;


          else


          {


              vector<int> print;


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


                  if (answer[i])


                     print.push_back(i+1);


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


                  cout<<print[i]<<char(i+1==print.size()?’\n’:’ ‘);


          }


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

留下评论

电子邮件地址不会被公开。