URAL1063[Domino Puzzle]

图论题,先要知道,一个无向图存在欧拉路,当且仅当此图为强连通图,且度数为奇的节点数为0或2。


然后要做的就是先将图强联通,然后贪心加边。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-4-6


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


{


      static const int oo=~(1<<31);


      static const int SIDE=6;


      vector<vector<int> > c;


      vector<int> degree;


      //GET PART


      vector<int> getid;


      void dfs(int id,stack<int>& s)


      {


           static vector<bool> visited(SIDE,false);


           if (!visited[id])


           {


              visited[id]=true;


              s.push(id);


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


                  if (c[id][i])


                     dfs(i,s);


           }


      }


      void get_part()


      {


           vector<vector<int> > part;


           getid.resize(SIDE);


           stack<int> s;


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


           {


               if (degree[i])


               {


                  dfs(i,s);


                  if (!s.empty())


                  {


                     part.push_back(vector<int>());


                     while (!s.empty())


                           part.back().push_back(s.top()),


                           getid[s.top()]=part.size(),


                           s.pop();


                  }


               }


           }


      }


      //END GET PART


      //GET ANSWER


      int answer;


      vector<pair<int,int> > list;


      bool check()


      {


           vector<vector<bool> > link(SIDE,vector<bool>(SIDE,false));


          


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


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


                   link[i][j]=c[i][j]||i==j;


          


           for (int k=0;k<SIDE;k++)


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


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


                       if (link[i][k]&&link[k][j])


                          link[i][j]=true;


          


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


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


                   if (degree[i]&&degree[j]&&(!link[i][j])) return false;


          


           return true;


      }


      void update(vector<pair<int,int> >& record)


      {


           int nanswer=0;


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


               nanswer+=record[i].first+1+record[i].second+1;


           vector<pair<int,int> > nlist(record);


          


           int counter=0;


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


               if (degree[i]%2) counter++;


           vector<int> add;


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


           {


               if (counter==2||counter==0) break;


               if (degree[i]%2)


               {


                  nanswer+=i+1;


                  counter–;


                  add.push_back(i);


               }


           }


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


               nlist.push_back(make_pair(add[i],add[i+1]));


          


           if (nanswer<answer)


           {


              answer=nanswer;


              list=nlist;


           }


      }


      void search(const vector<int>& getid)


      {


           static vector<pair<int,int> > record;


           set<int> part;


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


               if (getid[i])


                  part.insert(getid[i]);


          


           if (part.size()>1)


           {


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


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


                      if (degree[i]&&degree[j]&&getid[i]!=getid[j])


                      {


                         vector<int> ngetid=getid;


                         for (int k=0;k<SIDE;k++)


                             if (getid[k]==getid[i])


                                ngetid[k]=ngetid[j];


                         c[i][j]++;


                         c[j][i]++;


                         degree[i]++;


                         degree[j]++;


                         record.push_back(make_pair(i,j));


                         search(ngetid);


                         record.pop_back();


                         degree[j]–;


                         degree[i]–;


                         c[j][i]–;


                         c[i][j]–;


                      }


           }


           else


           {


               if (check())


                  update(record);


           }


      }


      //END GET ANSWER


      public:


      Application()


                   :c(SIDE,vector<int>(SIDE,0)),degree(SIDE,0)


      {


                   int N;


                   cin>>N;


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


                   {


                       int u,v;


                       cin>>u>>v;


                       c[u-1][v-1]++;


                       c[v-1][u-1]++;


                       degree[u-1]++;


                       degree[v-1]++;


                   }


      }


      int run()


      {


          get_part();


          answer=oo;


          search(getid);


          cout<<answer<<endl;


          cout<<list.size()<<endl;


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


              cout<<list[i].first+1<<” “<<list[i].second+1<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}