首先当然感谢管理员的审核qwq

这道题呢因为文字翻译不太准确,本蒟奉上完整题意:

本题思维要求较高,另外刘汝佳和一些大牛的博客代码比较难懂、复杂,窝就来一发NOIp幼儿园组都能看懂的好了2333

这道题有很多难点,我会在重点处划标记哒qwq


0.读入问题

woc小蒟蒻看题意都看了半天,一看数据A:FB;B:GC;D:GC;F:AGH;E:HD

夹着手的烟微微发抖...

让我们理理思路,首先珂以看到每个点与多个点有无向边,两次标记不多说; 其次是如何读取到:; 前后的点,这里用一个矩阵就可以存了(8个点)。

那我的思路是酱紫的:一次存一行后用一个数来表示是否找到:前的字母,然后对;前的字母建边。

还有一个坑就是可以观察到样例里的C这个点并没有建边,后面需要判断一下。

上代码和注释:

    char s[100];
    scanf("%s",s);
    if (s[0]=='#')
        return false;
    memset(g,0,sizeof(g)); //存储边
    memset(id,0,sizeof(id)); //标记字母是否出现
    tot=0; //出现的字母总数
    int pre=-1; //`:`前的字母是否出现
    for (int i=0; s[i]; i++)
    {
        if (s[i]==':')
            pre=s[i-1]-'A'; //如果出现就赋值(即s[i-1])
        else
        {
            if (s[i]==';') 
                pre=-1; //同时标记一下`;`
            if (pre!=-1) //如果这里改变了值,就说明找到了`:`前的点
            {
                g[pre][s[i]-'A']=true;
                g[s[i]-'A'][pre]=true; //建无向边
            }
        }
        if (s[i]>='A' && s[i]<='Z')
            id[s[i]-'A']=true; //对每一次出现的字母标记一下,因为最后输出按字典序,所以先按字典序排好
    }

那么到这里建边已经完成了,由于按字典序输出就把出现的点按字典序存在search数组里:

for (int i=0; i<26; i++)
        if (id[i])
            search[tot++]=i; //tot记录出现字母的总数,然后按字典序存储

1.主函数处理

这部分主要就是思路问题,我们每次dfs出当前最大带宽,然后与最大带宽比较更新就好了,注意每次flag数组清空

int main()
{
    while (init())
    {
        best_dist=26;
        memset(flag,0,sizeof(flag));
        dfs(0,0);
        for (int i=0; i<tot; i++)
            printf("%c ",best[i]+'A');
        printf("-> %d\n",best_dist);//按照格式输出
    }
    return 0;
}

2.最优性剪枝dfs

这可谓是整个代码的核心,其实并不难想,首先我们处理dfs到这一步时是否完成,然后对带宽进行更新,有更小的取更小的。很多人题意不太理解,其实就是dfs出本次最大带宽,然后与目前最大带宽比较,选小者留下,就实现了最大带宽最小值

先给出一段判断是否完成的伪代码qwq:

void dfs(int step,int dist)//step表示步数,dist表示带宽
if (step==tot)//此时已经满足了要求,即与字母种数相同
{
    if (dist<best_dist)
    {
        for (int i=0; i<tot; i++)
            best[i]=ans[i];
        best_dist=dist;//此时更新掉最小带宽
    }
}

那么对于寻找部分,可以采用最优性剪枝,因为一旦找出dist>=best_dist,下一次就不用往下寻找了

那么这就是代码核心

for (int j=0; j<step; j++)
    if (g[ans[j]][search[i]])
    {
        if (step-j>=best_dist)
        {
            check_ok=false;//记录,表示下次不用往下寻找
            break;//直接brak
        }
        if (step-j>cur_max_dist)
            cur_max_dist=step-j;//更新一下这个点的dist
    }

那么根据题意,dfs很快就能出来辣

void dfs(int step,int dist)
{
    if (step==tot)
    {
        if (dist<best_dist)
        {
            for (int i=0; i<tot; i++)
                best[i]=ans[i];
            best_dist=dist;
        }
    }
    else
    {
        for (int i=0; i<tot; i++)
        {
            if (!flag[search[i]])//还没有标记过这个字母
            {
                bool check_ok=true;//下次是否需要寻找
                int cur_max_dist=0;//当前点的dist
                for (int j=0; j<step; j++)
                    if (g[ans[j]][search[i]])
                    {
                        if (step-j>=best_dist)
                        {
                            check_ok=false;
                            break;
                        }
                        if (step-j>cur_max_dist)
                            cur_max_dist=step-j;
                    }
                if (check_ok)
                {
                    flag[search[i]]=true;
                    ans[step]=search[i];//记录ans数组
                    dfs(step+1,max(dist,cur_max_dist));
                    flag[search[i]]=false;//重新标记为false,warning:如果不标记代表着永远不能再碰到这个点
                }
            }
        }
    }
}

那么此时代码已经能愉快的实现啦!奉上AC代码(珂参考前文讲解食用):

#include <cstdio>
#include <cstring>
#define max(a,b) ((a)>(b)?(a):(b)) 
using namespace std;
bool g[30][30];
bool id[30];
int search[30];
int tot;
bool init()
{
    char s[100];
    scanf("%s",s);
    if (s[0]=='#')
        return false;
    memset(g,0,sizeof(g));
    memset(id,0,sizeof(id));
    tot=0;
    int pre=-1;
    for (int i=0; s[i]; i++)
    {
        if (s[i]==':')
            pre=s[i-1]-'A';
        else
        {
            if (s[i]==';')
                pre=-1;
            if ( pre!=-1)
            {
                g[pre][s[i]-'A']=true;
                g[s[i]-'A'][pre]=true;
            }
        }
        if (s[i]>='A' && s[i]<='Z')
            id[s[i]-'A']=true;
    }
    for (int i=0; i<26; i++)
        if (id[i])
            search[tot++]=i;
    return true;
}
int ans[26],best[26],best_dist;
bool flag[26];
void dfs(int step,int dist)
{
    if (step==tot)
    {

        if (dist<best_dist)
        {
            for (int i=0; i<tot; i++)
                best[i]=ans[i];
            best_dist=dist;
        }
    }
    else
    {
        for (int i=0; i<tot; i++)
        {
            if (!flag[search[i]])
            {
                bool check_ok=true;
                int cur_max_dist=0;
                for (int j=0; j<step; j++)
                    if (g[ans[j]][search[i]])
                    {
                        if (step-j>=best_dist)
                        {
                            check_ok=false;
                            break;
                        }
                        if (step-j>cur_max_dist)
                            cur_max_dist=step-j;
                    }
                if (check_ok)
                {
                    flag[search[i]]=true;
                    ans[step]=search[i];
                    dfs(step+1,max(dist,cur_max_dist));
                    flag[search[i]]=false;
                }
            }
        }
    }
}
int main()
{
    while (init())
    {
        best_dist=26;
        memset(flag,0,sizeof(flag));
        dfs(0,0);
        for (int i=0; i<tot; i++)
            printf("%c ",best[i]+'A');
        printf("-> %d\n",best_dist);
    }
    return 0;
}