解题报告 sgu 101

译题:

多米诺 ——一种用木头或者其他材料做的小方块进行的游戏,其中每个小方块面上通常标记点数或分数。这些小方块被称作骨牌,多米诺。有时用骨片,用卡片,甚至用人。
每个小块的表面被一条线分割成两部分,每一部分都写上了可能成对的号码。


在差不多所有的现代多米诺骨牌游戏中,比赛原则是要使两个标有相同或成对的号码的小方块首尾相接应。

——《大英百科全书》

给你一些多米诺骨牌,每块的两部分都标记上 0 到 6 的号码,你的任务是把这些骨牌排列在一条直线上,使得相邻骨牌的相邻部分有同样的号码。骨牌可以左右翻转。

输入

第一行包括一个整数 N (1 ≤ N ≤ 100) 表示骨牌总数。接下来 N 行描述每一块骨牌两部分的号码,每行两个 0 - 6 的数,用空格隔开。

输出

如果不存在这样的方案,输出 “No solution”。如果方案存在,输出任意一种符合要求的方案。输出方案时应该从左到右描述骨牌的排列,每行输出用空格隔开的一个整数和一个字符,分别表示骨牌的编号和是否翻转骨牌,(+表示不翻转,-表示翻转)。

样例输入

5
1 2
2 4
2 4
6 4
2 1
样例输出

2 -
5 +
1 +
3 +
4 -

方法,欧拉路,话说这是本人的第一个欧拉路撒。。。。。

//sgu 101 欧拉路
//任取一个奇数度的点,开始下面的步骤
//如果该点没有相连的点,就将该点加进路径中然后返回。
//如果该点有相连的点,就列一张相连点的表然后遍历它们直到该点没有相连的点。(遍历一个点,删除一个点)
//处理当前的点,删除和这个点相连的边, 在它相邻的点上重复上面的步骤,把当前这个点加入路径中.

program ACRush;
var n:longint;
a:array[0..10,0..10]of longint;
t:array[0..10]of longint;
path:array[0..202]of longint;
v:array[0..101]of boolean;
i,j,k,tot,t1,t2,now:longint;
p:array[0..202,1..4]of longint;
q:array[0..10]of longint;

procedure add(x,y:longint);
begin
inc(a[x,y]);
inc(a[y,x]);
inc(t[x]);
inc(t[y]);
end;        //一定要按无向边加,t 存的是每一个点上的边数。

procedure dfs(x:longint);
var i:longint; flag:boolean;
begin
if t[x]=0 then
begin
inc(now);
path[now]:=x;
exit;
end;

repeat
flag:=false;
for i:=0 to 6 do
if a[x,i]>0 then
begin
flag:=true;
dec(a[x,i]);
dec(a[i,x]);      //删边
dec(t[x]);
dec(t[i]);
dfs(i);
end;
until not flag;

for i:=0 to 6 do
begin
dec(t[i],a[x,i]);
a[x,i]:=0;      //理论上讲,这个不用加,上面删边可以删干净,但这个必须加,不然过不去,o(╯□╰)o
a[i,x]:=0;
end;

t[x]:=0;
inc(now);
path[now]:=x;
end;

procedure quicksortp(l,r:longint);
var x,i,j:longint;
begin
i:=l; j:=r; x:=p[(l+r) shr 1,1];
repeat
while p[i,1]<x do inc(i);
while x<p[j,1] do dec(j);
if i<=j then
begin
p[0]:=p[i]; p[i]:=p[j]; p[j]:=p[0];
inc(i); dec(j);
end;
until i>j;
if l<j then quicksortp(l,j);
if i<r then quicksortp(i,r);
end;

procedure print(x,y:longint);
var i:longint;
begin
for i:=q[x] to n+n do
if p[i,1]<>x then break
else
if not v[p[i,4]] then
if p[i,2]=y then          //我的输出搞得很麻烦,事实上是我欧拉路求对了,输出调了 N 久。
begin
if p[i,3]=1 then writeln(p[i,4],' ','+') else writeln(p[i,4],' ','-');
v[p[i,4]]:=true;
exit;
end;
end;

begin
readln(n);
for i:=1 to n do
begin
readln(j,k);
add(j,k);
p[i,1]:=j;
p[i,2]:=k;
p[i,3]:=1;
p[i,4]:=i;
p[i+n,1]:=k;
p[i+n,2]:=j;
p[i+n,3]:=2;
p[i+n,4]:=i;
end;

k:=0;        // k 为奇度点个数
for i:=0 to 6 do
if t[i] mod 2 <> 0 then
begin
inc(k);
if t1=0 then t1:=i else t2:=i;
end;

if (k<>0) and (k<>2) then
begin
writeln('No solution');
halt;
end;

now:=0;
if k=0 then t1:=p[1,1];    //此时,任选一个点开始。
dfs(t1);
for i:=0 to 6 do
if t[i]>0 then
begin
writeln('No solution');      //不连通
halt;
end;


quicksortp(1,n+n);
q[p[1,1]]:=1;
for i:=2 to n+n do
if p[i,1]<>p[i-1,1] then q[p[i,1]]:=i;    //就是那个悲剧的输出。。。

for i:=1 to now-1 do print(path[i],path[i+1])
end.

原文地址:https://www.cnblogs.com/SueMiller/p/2504256.html