http://poj.org/problem?id=1041

用 G[u][weight] = v 存图即可。

/*94ms,576KB*/

const int mx = 45;
const int mxm = 1995;

int G[mx][mxm]; /// 用 G[u][weight] = v 存图
int deg[mx];
bool vis[mxm];

vector<int> ans;
#define from first
#define to second

void init()
{
    mem(G, 0);
    mem(deg, 0);
    mem(vis, 0);
}

bool ok(int &start)
{
    int i;
    rForr(i, mx - 1, 1)
    {
        if (deg[i]) start = i;
        if (deg[i] & 1) return false;
    }
    return true;
}

void dfs(int u)
{
    int v;
    Forr(v, 1, mxm) if (!vis[v] && G[u][v])
    {
        vis[v] = true;
        dfs(G[u][v]);
        ans.PB(v);
    }
}

bool solve(int m)
{
    int start;
    if (!ok(start)) return false;
    ans.clear();
    dfs(start);
    return ans.size() == m;
}

int main()
{
    int m, i, u, v, id;
    while (SII(u, v), u)
    {
        init();
        m = 0;
        do
        {
            SI(id);
            G[u][id] = v, G[v][id] = u, ++deg[u], ++deg[v];
            ++m;
        }
    while (SII(u, v), u);
        if (!solve(m)) puts("Round trip does not exist.");
        else {rPA(ans, i, ans.size());}
    }
    return 0;
}

Comments

comments powered by Disqus