andyli

题解 UVA10054 【The Necklace】
如果把珠子看成点,似乎无法把题目转化成一个经典的、可以有效解决的问题,但如果把每种颜色看成一个结点,每个珠子的两半...
扫描右侧二维码阅读全文
24
2019/06

题解 UVA10054 【The Necklace】

如果把珠子看成点,似乎无法把题目转化成一个经典的、可以有效解决的问题,但如果把每种颜色看成一个结点,每个珠子的两半连一条有向边,则题目转化为了欧拉回路问题,可以在线性时间内解决。通过此题,数学建模的重要性可见一斑。
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 50;

struct Edge
{
    int u, v;
    Edge(int u = 0, int v = 0) : u(u), v(v) {}
};

vector<Edge> ans;
int G[maxn + 1][maxn + 1], cnt[maxn + 1], n;
void dfs(int u)
{
    for (int v = 1; v <= maxn; v++)
        if (G[u][v])
        {
            G[u][v]--, G[v][u]--;
            dfs(v);
            ans.emplace_back(u, v);
        }
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int kase = 1; kase <= T; kase++)
    {
        scanf("%d", &n);
        memset(G, 0, sizeof(G));
        memset(cnt, 0, sizeof(cnt));
        int start = -1;
        for (int i = 0; i < n; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            G[u][v]++, G[v][u]++;
            cnt[u]++, cnt[v]++;
            start = u;
        }
        // 无向图的欧拉回路
        bool solved = true;
        for (int i = 1; i <= maxn; i++)
            if (cnt[i] & 1)
            {
                solved = false;
                break;
            }  // 检查度数
        if (solved)
        {
            ans.clear();
            dfs(start);
            if (ans.size() != n || ans[0].v != ans[ans.size() - 1].u)
                solved = false;
        }
        printf("Case #%d\n", kase);
        if (!solved)
            printf("some beads may be lost\n");
        else
            for (int i = ans.size() - 1; i >= 0; i--)
                printf("%d %d\n", ans[i].u, ans[i].v);

        if (kase < T)
            printf("\n");
    }
    cin >> ws;
    return 0;
}
Last modification:June 25th, 2019 at 11:27 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment