CodeForces 114B 【STL应用】

思路：

原来string类能sort 和 swap....太强了....

注意：字典序最小输出，因为某个地方写挫了，sort了n发，代码挫。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int tol;

map<string,int>id;

map<int,string>xs;

string ss[20],sss[20];

bool ma[20][20];

int main()

{

    string t;

    string s;

    int n,kk;

    id.clear();

    xs.clear();

    tol=0;

    cin>>n>>kk;

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

        cin>>sss[i];

    sort(sss,sss+n);

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

    {

        id[sss[i]]=i;

        xs[i]=sss[i];

    }

    memset(ma,false,sizeof(ma));

    while(kk--)

    {

        cin>>s>>t;

        ma[id[s]][id[t]]=ma[id[t]][id[s]]=true;

    }

    vector<int> k,res;

    int ans=0;

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

    {

        k.clear();

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

        {

            if(i&(1<<j))

                k.push_back(j);

        }

        int sz=k.size();

        bool flag=true;

        for(int p=0; p<sz; p++)

            for(int q=0; q<sz; q++)

                if(ma[k[p]][k[q]])

                    flag=false;

        if(flag&&ans<sz)

        {

            res.clear();

            ans=sz;

            for(int p=0; p<sz; p++)

                res.push_back(k[p]);

        }

    }

    int num=res.size();

    printf("%d\n",num);

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

        ss[i]=xs[res[i]];

    sort(ss,ss+num);

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

        cout<<ss[i]<<endl;

    return 0;

}

巴特西

CodeForces 114B 【STL应用】

最新文章

热门文章