1323. Classmates 夜

http://acm.timus.ru/problem.aspx?space=1&num=1323

没有想那么多  直接暴力 dfs

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#define LL long long
#define sint short int
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int N=105;
const int INF=0x3f3f3f3f;
vector<int>a[N];
bool had[N];
struct node
{
    int p,t;
}mem[N],ans[N];
bool link[N][N];
map<string,int>mt;
string s[N];
int n,T;
void dfs(int i,int j,int num,int t1)
{
    if(num==n)
    {
        if(t1<T)
        {
            T=t1;
            for(int i=0;i<n;++i)
            {ans[i].p=mem[i].p;ans[i].t=mem[i].t;}
        }
        return ;
    }
    int k=a[i][j];
    bool flag=false;
    for(int l=0;l<n;++l)
    if(!had[l]&&link[k][l])
    {
        flag=true;
        had[l]=true;
        a[i+1].push_back(k);
        a[i+1].push_back(l);
        mem[l].p=k;
        mem[l].t=i+1;
        if(j==a[i].size()-1)
        dfs(i+1,0,num+1,max(t1,mem[l].t));
        else
        dfs(i,j+1,num+1,max(t1,mem[l].t));
        a[i+1].erase(a[i+1].end()-1);
        a[i+1].erase(a[i+1].end()-1);
        had[l]=false;
    }
    if(flag==false)
    {
        if(j==a[i].size()-1)
        dfs(i+1,0,num,t1);
        else
        dfs(i,j+1,num,t1);
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    int m;
    cin>>n>>m;
    memset(link,false,sizeof(link));
    int k=0;
    while(m--)
    {
        string s1,s2;
        cin>>s1>>s2;
        if(mt.find(s1)==mt.end())
        {s[k]=s1;mt[s1]=k++;}
        if(mt.find(s2)==mt.end())
        {s[k]=s2;mt[s2]=k++;}
        link[mt[s1]][mt[s2]]=true;
        link[mt[s2]][mt[s1]]=true;
    }
    string st;
    cin>>st;
    if(n==1)
    {cout<<"0"<<endl;return 0;}
    k=mt[st];
    mem[k].p=-1;
    mem[k].t=0;
    a[0].push_back(k);
    memset(had,false,sizeof(had));
    had[k]=true;
    T=INF;
    dfs(0,0,1,0);
    cout<<T<<endl;
    for(int i=1;i<=T;++i)
    {
        int tmp=0;
        for(int j=0;j<n;++j)
        if(ans[j].t==i)
        ++tmp;
        cout<<tmp<<endl;
        for(int j=0;j<n;++j)
        if(ans[j].t==i)
        cout<<s[ans[j].p]<<" "<<s[j]<<endl;
    }
    return 0;
}