URAL/1323

来自"NOCOW"

简单DP,(2^n)*(2^n)的状态。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#define get(x,i) (((x)>>((i)-1))&1)
#define delta(i) (1<<((i)-1))
#define merge(x,y) (((x)<<(n))|(y))
int n,m,x,y,d,l=0,r=0,tot=0,ans=0,head,target,level[11]={0};
int f[1<<10][1<<10],p[1<<20],Q[1<<20],edge[11][11][2];
char na[11][22],s[22],t[22];
bool map[11][11]={false};
int find(char s[22])
{
    for (int i=1;i<=tot;++i)
        if (!strcmp(s,na[i]))
            return i;
    memcpy(na[++tot],s,sizeof(char [22]));
    return tot;
}
void insert(int x,int y,int d,int pre)
{
    if (d < f[x][y])
    {
        p[Q[++r]=merge(x,y)]=pre;
        f[x][y]=d;
    }
}
int count(int x)
{
    for (int i=1;i<=n;++i)
        if (get(x,i))
            return i;
}
void print(int x,int y,int last)
{
    int pre=p[merge(x,y)];
    if (pre)  print(pre>>n,pre&target,merge(x,y));
    if (f[last>>n][last&target] > tot)  ++tot;
    else
    {
        ++level[tot];
        edge[tot][level[tot]][0]=count(y^(last&target));
        edge[tot][level[tot]][1]=count(x^(last>>n));
    }
}
int main()
{
    scanf("%d%d%*c",&n,&m);
    if (n == 1)
    {
        printf("0\n");
        return 0;
    }
    for (int i=1;i<=m;++i)
    {
        scanf("%s%s%*c",s,t);
        x=find(s);
        y=find(t);
        map[x][y]=map[y][x]=true;
    }
    scanf("%s",s);
    target=delta(n+1)-1;
    for (int i=0;i<=target;++i)
        for (int j=0;j<=target;++j)
            f[i][j]=11;
    head=delta(find(s));
    insert(head,head,tot=1,0);
    while (l++ < r)
    {
        d=f[x=(Q[l]>>n)][y=(Q[l]&target)];
        for (int i=1;i<=n;++i)
            if (get(y,i))
                for (int j=1;j<=n;++j)
                    if (map[i][j] && (get(x,j)^1))
                        insert(x|delta(j),y^delta(i),d,merge(x,y));
        insert(x,x,d+1,merge(x,y));
    }
    for (int i=1;i<=target;++i)
        if (f[target][i] < f[target][ans])
            ans=i;
    printf("%d\n",f[target][ans]);
    print(target,ans,0);
    for (int i=1;i<=f[target][ans];++i)
    {
        printf("%d\n",level[i]);
        for (int j=1;j<=level[i];++j)
            printf("%s %s\n",na[edge[i][j][0]],na[edge[i][j][1]]);
    }
    return 0;
}
//by zzy