SGU101 解题手记
　　题目看完有似曾相识的感觉，不知道在什么地方见过这个题，直接就想到应该转化为欧拉路而不是哈密顿路。转化是这样的：以0-6这7个数字（注意是7个数字）为顶点，一张骨牌上作为一条边，即在骨牌上的两个数字之间连边。然后求一条欧拉路，再对照欧拉路，把骨牌的顺序排出来。
　　欧拉路要求所有的边都走一遍，这样所有的骨牌就被串起来了。算法复杂度O(n^2)。
　　编码中遇到了一个问题，list的成员不能是数组。具体原因我没弄明白，只知道跟new有关。解决的办法是把数组封装到类里。
　　Sumbit 1: PE on 1。忘记在骨牌序号和+/-之间空格。
　　Sumbit 2: WA on 1。将C风格字符串错写成单引号，导致输出无效。
　　Sumbit 3: WA on 4。将“奇点有两个以上没有欧拉路”错写为“奇点有奇数个没有欧拉路”。
　　Sumbit 4: WA on 4。修改过程中计数奇点的变量初值错了。
　　Sumbit 5: WA on 4。仍然WA就很郁闷了，阅读Amber的程序后想起来了，我没有判断图是否连通……然后……发现了一处更晕的错误……我把翻转和不翻转都写的+号……这样都能过到4，真无语了。另外发现了一个不良习惯——我喜欢写i++，但按照C++ Primer的说法，没事儿要写++i，因为i++要额外做一项保存变量初值的工作。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

//AC
#include <iostream>
#include <list>
using namespace std;
 
struct domino
{
    int d[3];
};
list<domino> dominoes;
list<int> euler;
int graph[7][7];
bool visited[7];
 
void build_euler(int v)
{
    visited[v]=true;
    bool nopath=true;
    for (int i=0;i<=6;++i)
        while (graph[v][i])
        {
            nopath=false;
            --graph[v][i]; --graph[i][v];
            build_euler(i);
        }
    euler.push_back(v);
}
 
void print_ans()
{
    int a=0,b=*euler.begin();
    list<int>::iterator i=euler.begin(); ++i;
    for (;i!=euler.end();++i)
    {
        a=b; b=*i;
        for (list<domino>::iterator j=dominoes.begin();j!=dominoes.end();++j)
            if (a==j->d[1] and b==j->d[2])
            {
                cout<<j->d[0]<<" +"<<endl;
                dominoes.erase(j); break;
            }
            else if (a==j->d[2] and b==j->d[1])
            {
                cout<<j->d[0]<<" -"<<endl;
                dominoes.erase(j); break;
            }
    }
}
 
void build_dominoes_graph()
{
    int n,i;
    domino t;
    cin>>n;
    for (i=1;i<=n;++i)
    {
        cin>>t.d[1]>>t.d[2]; t.d[0]=i;
        dominoes.push_back(t);
        ++graph[t.d[1]][t.d[2]]; ++graph[t.d[2]][t.d[1]];
    }
}
 
inline void init()
{
    memset(graph,0,sizeof(graph)/sizeof(int));
    memset(visited,0,sizeof(visited)/sizeof(bool));
}
 
int main()
{
    init();
    build_dominoes_graph();
    int startp=-1,oddp=-1,notour=0,degree;
    for (int i=0;i<=6;++i)
    {
        degree=0;
        for (int j=0;j<=6;++j)
            degree+=(graph[i][j]);
        notour+=(degree & 1);
        if (degree) startp=i;
        else visited[i]=true;
        if (degree & 1) oddp=i;
    }
    if (notour>2)
    {
        cout<<"No solution"<<endl;
        return 0;
    }
    if (oddp!=-1) startp=oddp;
    build_euler(startp);
    bool visitedall=true;
    for (int i=0;i<=6;++i)
        visitedall&=visited[i];
    if (!visitedall)
    {
        cout<<"No solution"<<endl;
        return 0;
    }
    /*debug*/
 
    /*enddebug*/
    print_ans();
    return 0;
}