poj 2732 Countdown（East Central North America 2005）

题意：建一个家庭树，找出有第d代子孙的名字，按照要求的第d代子孙的数从大到小输出三个人名，如果有一样大小子孙数的，就按字母序从小到大将同等大小的都输出，如果小于三个人的就全输出。

题目链接：http://poj.org/problem?id=2732

分析：数据量很小，直接建树，枚举暴力输出。我直接套模板用map建树的。

注意：1.每次测试数据时要清空map和vector！！！

2.注意输出要从大到小输出答案，如果答案有一样的按名字的字母序从小到大输出。答案用vector保存，vector排序：sort(v.begin(),v.end(),cmp);

3.注意嵌套模板的使用，map<string,vector<string> >fa;

另，关于建树，可以直接用int类型代替名字的string类型，给每个名字赋予一个编号。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <cmath>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 string name[];

 map<string,int>mp;

 map<string,vector<string> >fa;

 vector<pair<string,int> >ans;

 vector<string>v;

 int fin(string na,int gen)

 {

     int ans=;

     if(gen==)

         return ;

     for(int i=;i<mp[na];i++)

     {

        if(gen>=)

        ans+=fin(fa[na][i],gen-);

     }

     return ans;

 }

 int cmp(pair<string,int>p1,pair<string,int>p2)

 {

     if(p1.second==p2.second)

         return p1.first<p2.first;

     return p1.second>p2.second;

 }

 int main()

 {

     int t,cnt=;

     cin>>t;

     while(t--)

     {

         fa.clear();   //每次样例注意清空数据

         ans.clear();

         mp.clear();

         int n,d;

         cin>>n>>d;

         int num;

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

         {

             cin>>name[i];

             cin>>num;

             string child;

             mp[name[i]]=num;

             v.clear();

             for(int j=;j<num;j++)

             {

                 cin>>child;

                 v.push_back(child);

             }

             fa[name[i]]=v;  //嵌套模板的使用

         }

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

         {

             int res=fin(name[i],d);

             if(res>)

                 ans.push_back(make_pair(name[i],res));

         }

         int len=ans.size();

         sort(ans.begin(),ans.end(),cmp);

         printf("Tree %d:\n",cnt);

         for(int i=;i<len;i++)   //注意答案的输出

         {

             if((i>)&&ans[i].second!=ans[i-].second)

                 break;

             cout<<ans[i].first<<" "<<ans[i].second<<endl;

         }

         cnt++;

     }

     return ;

 }

巴特西

poj 2732 Countdown（East Central North America 2005）

最新文章

热门文章