URAL1045[A funny game]

是极大极小搜索(true大false小),然后还是树形动规,还是博弈论,很有意思的题目(指NOCOW上的翻译)。


然后,提醒一下,有解时输出的L为与K连接且是必胜态的最小编号。我开始没读懂,输的不是这样的点,结果WA了两三次。无语。


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,K;


      vector<vector<int> > link;


      vector<bool> win;


      void go(int node,bool isMe,int father=-1)


      {


           for (int i=0;i<link[node].size();i++)


               if (link[node][i]!=father)


                  go(link[node][i],!isMe,node);


           if (isMe)


           {


              win[node]=false;


              for (int i=0;i<link[node].size();i++)


                  if (link[node][i]!=father)


                     win[node]=win[node] or win[link[node][i]];


           }


           else


           {


               win[node]=true;


               for (int i=0;i<link[node].size();i++)


                   if (link[node][i]!=father)


                      win[node]=win[node] and win[link[node][i]];


           }


      }


      public:


      Application()


      {


                    cin>>N>>K;


                    link.resize(N);


                    for (int i=1,v,u;i<N;i++)


                        cin>>v>>u,link[v-1].push_back(u-1),link[u-1].push_back(v-1);


      }


      int run()


      {


          win.resize(N,false);


          go(K-1,true);


          if (win[K-1])


          {


             int gohere=N;


             for (int i=0;i<link[K-1].size();i++)


                 if (win[link[K-1][i]])


                    if (gohere>link[K-1][i])


                       gohere=link[K-1][i]+1;


             cout<<“First player wins flying to airport “<<gohere<<endl;


          }


          else cout<<“First player loses”<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}