# Livestock Lineup

· 阅读需 7 分钟

## 题目​

Every day, Farmer John milks his 8 dairy cows, named Bessie, Buttercup, Belinda, Beatrice, Bella, Blue, Betsy, and Sue.

The cows are rather picky, unfortunately, and require that Farmer John milks them in an order that respects $N$ constraints. Each constraint is of the form "$X$ must be milked beside $Y$", stipulating that cow $X$ must appear in the milking order either directly after cow $Y$ or directly before cow $Y$.

Please help Farmer John determine an ordering of his cows that satisfies all of these required constraints. It is guaranteed that an ordering is always possible. If several orderings work, then please output the one that is alphabetically first. That is, the first cow should have the alphabetically lowest name of all possible cows that could appear first in any valid ordering. Among all orderings starting with this same alphabetically-first cow, the second cow should be alphabetically lowest among all possible valid orderings, and so on.

$1\le N\le 7$256MB2.0s

## 程序​

/** * Adopted from official solution at * http://www.usaco.org/current/data/sol_lineup_bronze_dec19.html */#include <iostream>#include <fstream>#include <vector>#include <algorithm>using namespace std;string names[8] = {"Beatrice", "Belinda", "Bella", "Bessie", "Betsy", "Blue", "Buttercup", "Sue"};// beside_a 和 beside_b 中对应下标的奶牛表示一组约束关系vector<string> beside_a, beside_b;int n;int getID(string name) {    for (int i = 0; i < 8; i++)        if (names[i] == name)            return i;    return -1;}bool satisfies_constraints() {    for (int i = 0; i < n; i++)        if (abs(getID(beside_a[i]) - getID(beside_b[i])) != 1)            return false;    return true;}int main() {    ifstream fin("lineup.in");    ofstream fout("lineup.out");    fin >> n;    string a, b;    for (int i = 0; i < n; i++) {        fin >> a >> b >> b >> b >> b >> b;        beside_a.push_back(a);        beside_b.push_back(b);    }    // 遍历所有的8头奶牛的排列，输出第一个满足约束的解    do {        if (satisfies_constraints()) {            for (int i = 0; i < 8; i++)                fout << names[i] << endl;            return 0;        }    } while (next_permutation(names.begin(), names.end()));    return 0;}

#include <iostream>#include <fstream>using namespace std;struct cow {    int adj[2];  // 需要和这头奶牛相邻的奶牛的ID    int adjcnt;  // 这头奶牛一共有几个约束条件；决定了能否把它放在约束链的开头    bool chosen; // 是否已经进队} cows[8];string names[8] = {"Beatrice", "Belinda", "Bella", "Bessie", "Betsy", "Blue", "Buttercup", "Sue"};int getID(string name) {    for(int i = 0; i < 8; i++)        if(names[i] == name)            return i;    return -1;}int main() {    ifstream fin("lineup.in");    ofstream fout("lineup.out");    int n;    fin >> n;    string a, b;    for (int i = 0; i < n; i++) {        fin >> a >> b >> b >> b >> b >> b;        cows[getID(a)].adj[cows[getID(a)].adjcnt++] = getID(b);        cows[getID(b)].adj[cows[getID(b)].adjcnt++] = getID(a);    }    int prev = -1;    // 每次循环向队列中添加一头奶牛；如果上一头奶牛没有更多的约束条件了，则可以选择一头新的，否则选择需要和上一头相邻的奶牛    for (int _ = 0; _ < 8; _++) {        if (_ == 0 || cows[prev].adjcnt == 0) {            for (int i = 0; i < 8; i++) {                if (!cows[i].chosen && cows[i].adjcnt < 2) {                    cows[i].chosen = true;                    fout << names[i] << endl;                    prev = i;                    break;                }            }        } else if (cows[prev].adjcnt == 1) {            int i = cows[prev].adj[0];            cows[i].chosen = true;            // 这里的操作是在把cows[i]添加入队列的同时“删除”掉它已经满足的那条约束            cows[i].adjcnt--;            if(cows[i].adj[0] == prev)                cows[i].adj[0] = cows[i].adj[1];            fout << names[i] << endl;            prev = i;        }    }    return 0;}