Domino - SGU 101 （欧拉路径）

题目大意：这是一个多米诺骨游戏，这个游戏的规则就是一个连着一个，现在给出 N 个多米诺，每个多米诺两边都有一个编号，相邻的多米诺的编号要一致，当然多米诺是可以翻转的（翻转就加‘-’，不翻转是‘+’），输出一个多米诺的顺序，要从左往右。

分析：开始的是有以为是二分匹配，然后发现并不能匹配，无法分成两个集合，网络流也不能搞，最后百度才知道是欧拉路径（从一点出发经过所有的路径，每条路只走一次），这个算法倒也不难理解，感觉很巧妙，如果点的入度都是偶数的话，那么就是欧拉回路（可以从一个点出发然后，最后还可以回到这个点结束），如果把所有的多米诺的编号当做节点，那么每个多米诺就是一条边，问题就转换成裸的欧拉路径题目了，判断是否是欧拉路径的时候需要注意，这个图是否是联通的。

代码如下：

===================================================================================================

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

const int MAXN = ;

struct Bridge

{

    int u, v, next;

    int id, used;

}edge[MAXN];

int Head[MAXN], cnt;

int ans[MAXN], na;

void AddEdge(int u, int v, int id)

{

    edge[cnt].u = u;

    edge[cnt].v = v;

    edge[cnt].id = id;

    edge[cnt].used = false;

    edge[cnt].next = Head[u];

    Head[u] = cnt++;

    swap(u, v);

    edge[cnt].u = u;

    edge[cnt].v = v;

    edge[cnt].id = id;

    edge[cnt].used = false;

    edge[cnt].next = Head[u];

    Head[u] = cnt++;

}

void DFS(int k)

{

    for(int i=Head[k]; i!=-; i=edge[i].next)

    {

        if(edge[i].used == false)

        {

            edge[i].used = edge[i^].used = true;

            DFS(edge[i].v);

            ans[na++] = i;

        }

    }

}

int main()

{

    int N, u, v;

    scanf("%d", &N);

    memset(Head, -, sizeof(Head));

    cnt = , na=;

    int ru[MAXN] = {}, index=;

    for(int i=; i<=N; i++)

    {

        scanf("%d%d", &u, &v);

        AddEdge(u, v, i);

        ru[u]++, ru[v]++;

        index = u;

    }

    int sum = ;

    for(int i=; i<; i++)

    {

        if(ru[i] % )

        {

            sum ++;

            index = i;

        }

    }

    if(sum !=  && sum != )

        printf("No solution\n");

    else

    {

        DFS(index);

        if(na != N)

            printf("No solution\n");

        else

        {

            for(int i=; i<na; i++)

                printf("%d %c\n", edge[ans[i]].id, ans[i]% ? '+' : '-');

        }

    }

    return ;

}

巴特西

Domino - SGU 101 （欧拉路径）

最新文章

热门文章