http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=60
http://poj.org/problem?id=1270

枚举答案,检查是否与限制矛盾即可。(复杂度看上去高但实际上数据超弱..)

/*UVa: 0.019s*/
/*POJ: 16ms,168KB*/
const int mx = 27;

int n;
bool edge[mx][mx];
char s[mx], tmp[200];

bool checkTopo(char *s)
{
    int i, j;
    /// 检测有没有逆向边(与当前拓扑结果矛盾的边)
    rForr(i, n - 1, 1) rFor(j, i - 1) if (edge[s[i] & 31][s[j] & 31]) return false;
    return true;
}

int main()
{
    int i;
    bool ok = false;
    while (gets(tmp))
    {
        ok ? Pn() : ok = true;
        n = 0;
        for (i = 0; tmp[i]; ++i) if (tmp[i] != 32) s[n++] = tmp[i];
        s[n] = 0;
        sort(s, s + n);
        mem(edge, 0);
        mem(tmp, 0);
        gets(tmp);
        for (i = 0; tmp[i]; i += 4) edge[tmp[i] & 31][tmp[i + 2] & 31] = true;
        do if (checkTopo(s)) puts(s);
        while (next_permutation(s, s + n));
    }
    return 0;
}

Comments

comments powered by Disqus