http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=543&page=show_problem&problem=995

珠子视作点,还是视作边?
前者哈密顿回路,后者欧拉回路。

既然哈密顿回路是NP的,那就用欧拉回路做啦。

/*0.252s*/

const int mx = 51;

int n, G[mx][mx], deg[mx];
vector<p2> ans;
#define from first
#define to second

void euler(int u)
{
    int v;
    Forr(v, 1, mx) if (G[u][v])
    {
        --G[u][v], --G[v][u];
        euler(v);
        ans.PB(MP(u, v));
    }
}

bool solve(int start) /// 随意取一个(存在的)起点
{
    int i;
    Forr(i, 1, mx) if (deg[i] & 1) return false;
    ans.clear();
    euler(start);
    return ans.size() == n; /// 不需要判断首尾是否相同
}

int main()
{
    int t, cas = 0, u, v, start, i;
    SI(t);
    while (t--)
    {
        Pcas();
        SI(n);
        mem(G, 0);
        mem(deg, 0);
        For(i, n)
        {
            SII(u, v);
            ++G[u][v], ++G[v][u];
            ++deg[u], ++deg[v];
            start = u;
        }
        if (solve(start)) rFor(i, ans.size() - 1) PII(ans[i].from, ans[i].to);
        else puts("some beads may be lost");
        if (t) Pn();
    }
    return 0;
}

Comments

comments powered by Disqus