题解 P5833 【[USACO19DEC]Livestock Lineup牲畜阵容】

· · 题解

题解 P5833 【[USACO19DEC]Livestock Lineup牲畜阵容】

题意：已知8头奶牛，每头奶牛有一个名字。给定一个N，以及已知N头奶牛之间排列的关系，求所有符合要求的排列中，名字字典序最小的一个排列

这一道题我用的很奇怪的方法，有点想复杂了。其实可以用全排列直接算一遍的（我同学说是这么做的）

我用的是一个双向链表lb数组存奶牛之间的关系，再用de数组存每个奶牛的度（或者说是有几个和别的牛在一起的要求）。

然后从字典序小的往后遍历，如果度为0，则这个牛就是无拘无束的，可以直接排。如果度为1，就要排完了这个后，按照链表以这个牛为头的顺序，依次放下去。这个很容易证明是对的。如果先遍历到了链表的另一头，则这个方法肯定比从另一头开始字典序小，毕竟这一头的字典序比另一头小。度为2的不用管，因为他一定在某个链中间，这个链被排好了他也一定就被排好了。

另外，在往下搜的过程中，必须要打vis标记，这样才能保证你搜完了链表的一头以后不会再从另一头搜一遍……

如果还有看不懂的，看代码吧，注释很详细。

//Code by zimindaada in 20191220
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
int n;
char beat[] = "Beatrise", beli[] = "Belinde", bell[] = "Bella", bess[] = "Bessie", \
    bets[] = "Betsy", blue[] = "Blue", butt[] = "Buttercup";//因为cmp不能直接用"Bessie"来做参数所以搞了这个愚蠢的玩意儿……
inline bool cmp(char a[], char b[]){//我不太会用char数组，所以打了一个奇怪的cmp来代替==
    int l = strlen(b);
    for(int i = 0; i < l; ++i){
        if(a[i] != b[i]) return 0;
    }
    return 1;
}
inline int convert(char t[]){//为了方便，把名字按顺序转换成数字
    if(cmp(t, beat)) return 1;
    else if(cmp(t, beli)) return 2;
    else if(cmp(t, bell)) return 3;
    else if(cmp(t, bess)) return 4;
    else if(cmp(t, bets)) return 5;
    else if(cmp(t, blue)) return 6;
    else if(cmp(t, butt)) return 7;
    else return 8;
}
int de[10];//每个牛的度（或者说是每个牛已经和几个牛确定了关系）
int lb[10][2];//双向链表
bool vis[10];//vis标记
inline string back(int t){//从数字转换回字符串的函数
    if(t == 1) return "Beatrise";
    else if(t == 2) return "Belinde";
    else if(t == 3) return "Bella";
    else if(t == 4) return "Bessie";
    else if(t == 5) return "Betsy";
    else if(t == 6) return "Blue";
    else if(t == 7) return "Buttercup";
    else return "Sue";
}

//核心函数//
void dfs(int fa, int x){//fa代表上一个,x代表目前的
    //首先因为前面已经被选了，所以它必须被选
    cout << back(x) << endl;
    for(int i = 1; i <= de[x]; ++i){
        if(lb[x][i] != fa && !vis[lb[x][i]]){//确保搜到的不是上一个
            vis[lb[x][i]] = 1;
            dfs(x, lb[x][i]);
        }
    }
}

int main(){
    scanf("%d",&n);
    char s1[15], s2[15];//输入用变量
    for(int i = 1; i <= n; ++i){
        scanf("%s must be milked beside %s",s1, s2);//输入
        int x1 = convert(s1), x2 = convert(s2);
        lb[x1][++de[x1]] = x2; lb[x2][++de[x2]] = x1;//链表存
    }

    //核心代码//
    for(int i = 1; i <= 8; ++i){//遍历一遍八头牛

        //由字典序定义，前面越小字典序小，所以尽可能让更前面的更小
        if(vis[i]) continue;//如果遍历/dfs过了一遍，就跳过

        if(de[i] == 0){//如果没有关系
            //因为遍历到它，说明当前最好的方案就是选他，
            cout << back(i) << endl;//就可以直接放。
            vis[i] = 1;//记得打标记
        }else if(de[i] == 1){//如果有1个关系
            vis[i] = 1;
            //同上，但是因为它是一个链表的头，
            dfs(-1,i);//所以要用dfs遍历一遍链表（用for或while也行）
        }
    }
    return 0;
}

注：该代码有防抄措施，在题解非核心代码上的做了修改！