题目链接

http://acm.sgu.ru/problem.php?contest=0&problem=101

题目大意

多米诺骨牌,一种用小的方的木块或其他材料,每个都被一些点在面上标记,这些木块通常被称为骨牌。每个骨牌的面都被一条线分成两个方形,两边各有一定点数。N个多米诺骨牌,每个骨牌左右两侧分别有一个0~6的整数(骨牌可以旋转以调换其左右两数),求一种把这些骨牌从左到右排列的方案,使得所有相邻的两数字相等(即左边骨牌右侧的数字等于右边骨牌左侧的数字)。

题解

将0~6这7种牌面看作节点,把骨牌看作是连接两节点的无向弧,这样就组成了一个无向图(当然可能有重边),图中的一条欧拉路就对应一种方案。 

知识点

若图连同且度为奇数的节点不超过两个,则可以构造出欧拉路。先选一个度为奇数的节点(若没有就任选一个度为偶数的节点),以该节点为起点,深搜遍历所有的弧(每条弧只遍历一次),在每次回溯时将当前弧记录下来,记录的弧的排列就组成了一条欧拉路。 实际编程时,为便于输出方案,可将图中的边加上一个“权值”,为骨牌的编号。

代码

//
//  main.cpp
//  sgu
//
//  Site @haipz.com
//  Copyright (c) 2015年 林海鸿. All rights reserved.
//

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 100;
struct adge {
    int v, dir, next;
};
struct node {
    int v, dir;
};

adge f[N*2 + 5];
node ans[N + 5];
int first[N + 5], degree[N + 5];
bool used[N + 5];

void addEdge(int &cnt, int u, int v, int dir) {
    ++cnt;
    f[cnt].v = v;
    f[cnt].dir = dir;
    f[cnt].next = first[u];
    first[u] = cnt;
    return;
}

void dfs(int &cnt, int u) {
    for (int i = first[u]; i; i = f[i].next) {
        if (!used[(i + 1)/2]) {
            used[(i + 1)/2] = true;
            dfs(cnt, f[i].v);
            ++cnt;
            ans[cnt].v = (i + 1)/2;
            ans[cnt].dir = 1 - f[i].dir;
        }
    }
    return;
}

int main() {
    int n;
    scanf("%d", &n);
    memset(first, 0, sizeof(first));
    memset(degree, 0, sizeof(degree));
    
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(cnt, u, v, 1);
        addEdge(cnt, v, u, 0);
        ++degree[u], ++degree[v];
    }
    
    cnt = 0;
    int start = 0;
    for (int i = 0; i <= 6; ++i)
        if (degree[i] & 1) {
            ++cnt;
            start = i;
        }
    
    if (cnt > 2) {
        printf("No solution\n");
        return 0;
    }
    
    memset(used, false, sizeof(used));
    if (cnt == 0)
        for (int i = 0; i <= 6; ++i)
            if (degree[i]) {
                start = i;
                break;
            }
    cnt = 0;
    dfs(cnt, start);
    
    if (cnt != n) printf("No solution\n");
    else for (int i = 1; i <= n; ++i) printf("%d %c\n", ans[i].v, ans[i].dir == 1 ? '+' : '-');
    
    return 0;
}
转载保留版权:http://haipz.com/blog/i/6429 - 海胖博客