首页 > 代码库 > sgu 101 domino

sgu 101 domino

2024-07-04 14:53:16   235人阅读

    题意还算简洁明了，加上有道翻译凑过着读完了题。题意大体上是 给你 n 个多米诺骨牌， 给出每个骨牌两端的数字， 只有数字相同才可以推到， 比如 2-3和3-2。你可以旋转这些多米诺骨牌， 输出一个可以全部推到的方案， 如果没有 ，输出 No solution。

    第一眼看上去像爆搜， 但是 n 最大到100， 时限竟然只有0.25s，铁定超时， 换个思路， 想不出来， 看了题解，才发现原来是图论题，我们把 0~6 当做点，把每个骨牌当做边， 这样构成了一个图， 我们需要求得就是 遍历所有的边且不重复。

    这个可以算是一个 欧拉路 模板题，注意，是 欧拉路， 不是欧拉回路 ，被坑了好久。

    欧拉路和欧拉回路都是一笔画问题， 两者都需要满足一个必要条件 ： 度数为奇数的要么没有， 要么有2个。 度数就是这个点连得边的条数。

    先说欧拉回路， 欧拉回路由于需要回到原点， 所以一定没有度数为奇的点， 只要从任意一点 dfs ，走过的边不再走， 直到无边可走， 就是欧拉回路，此时一定是在原点。

    但是，欧拉路不同， 欧拉路可以不回到原点， 这导致 dfs 有可能导致死胡同 ， 看一个例子 ：

在这个例子里， 如果从 3 开始 dfs, 我们有可能回走到 2 ，然后走到 1， 这时我们发现无路可走了， 但这本应是一个一笔画， 只要从 1 出发就可以了，但是我们在程序里不好判断从哪个点开始， 所以， 引入欧拉路的求法：

    从任意一个度数为奇的点开始，仍然 dfs，但是 我们不一开始就把这个点加入答案， 而是先任选和这个点相连的一条边， 继续向下dfs， 然后在把这个店加入答案，就等于是倒序输出。这样很巧妙的解决了上面说的问题。光这么说可能不太好理解，一看代码立刻就能明白。

void ss(int now)
{
    遍历每一条和这个点相连的边
    {
        标记已经走过这条边，以后不再走
                ss(和它相邻的点);
        把现在这个点加入答案
    }
}

    如此一来就可以了， 但要注意，要判断此图是否联通， 只需判断你求出的边数和骨牌数是否相等就行了，上代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define N 110 * 2
#define M 10
using namespace std;

int n, du[M] = {0};
int p[M], next[N*2], v[N*2], zheng[N*2], bnum = -1, kexing[N*2], num[N*2];
int ans[N][2], ansnum = 0;

void addbian(int x, int y, int now)
{
    bnum++; next[bnum] = p[x]; p[x] = bnum;
    v[bnum] = y; zheng[bnum] = 1; kexing[bnum] = 1; num[bnum] = now;
    bnum++; next[bnum] = p[y]; p[y] = bnum;
    v[bnum] = x; zheng[bnum] = 0; kexing[bnum] = 1; num[bnum] = now;
}

void ss(int now)
{
    int k = p[now];
    while (k != -1)
    {
        if (kexing[k])
        {
            kexing[k] = 0; kexing[k^1] = 0;
            ss(v[k]);
            ansnum++;
            ans[ansnum][0] = num[k^1];
            ans[ansnum][1] = zheng[k^1];
        }
        k = next[k];
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i <= 6; ++i) p[i] = -1;
    for (int i = 1; i <= n; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        du[x]++; du[y]++;
        addbian(x, y, i);
    }
    if (n == 0)
    {
        printf("No solution\n");
        return 0;
    }
    int jnum = 0, start = -1;
    for (int i = 0; i <= 6; ++i)
        if (du[i] % 2 != 0)
        {
            jnum++; start = i;
        }
    if (jnum !=0 && jnum != 2)
    {
        printf("No solution\n");
        return 0;
    }
    if (start == -1)
        for (int i = 0; i <= 6; ++i)
            if (du[i] != 0) start = i;
    ss(start);
    if (ansnum < n)
    {
        printf("No solution\n");
        return 0;
    }
    for (int i = 1; i <= n; ++i)
    {
        printf("%d ",ans[i][0]);
        if (ans[i][1]) printf("+\n");
        else printf("-\n");
    }
}

 


联系
我们