現在開始轉戰SGU,接著水題。
解法：歐拉路，模型很容易想到，記得UVA上有一道類似的叫The necklace。題目雖然簡單，細節的調試花了我不少時間，手感還沒恢復啊。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 105
int p1[N], p2[N], g[10][10], d[N], ans[N], top;
void Pre()
{
top = 0;
memset(g, 0, sizeof(g));
memset(d, 0, sizeof(d));
memset(p1, -1, sizeof(p1));
memset(p2, -1, sizeof(p2));
}
void Euler(int u)
{
for(int i = 0; i < 7; i++)
if(g[u][i])
{
g[u][i]--, g[i][u]--;
d[i]--, d[u]--;
Euler(i);
}
ans[top++] = u;
}
void Solve(int n)
{
int odd = 0, u;
for(int i = 0; i < 7; i++)
{
if(d[i] & 1)
{
odd++;
u = i;
}
}
if(odd && odd != 2)
{
puts("No solution");
return;
}
for(int i = 0; i < 7; i++)
{
if(odd)
{
if(d[i] & 1)
{
Euler(i);
break;
}
}
else if(d[i])
{
Euler(i);
break;
}
}
if(top != n + 1)
{
puts("No solution");
return;
}
for(int k = 1; k < top; k++)
{
int a, b;
a = ans[k - 1], b = ans[k];
for(int i = 0; i < n; i++)
{
if(a == p1[i] && b == p2[i])
{
printf("%d +\n", i + 1);
p1[i] = p2[i] = -1;
break;
}
else if(a == p2[i] && b == p1[i])
{
printf("%d -\n", i + 1);
p1[i] = p2[i] = -1;
break;
}
}
}
}
int main()
{
int n, a, b;
while(~scanf("%d", &n))
{
Pre();
for(int i = 0; i < n; i++)
{
scanf("%d %d", &a, &b);
p1[i] = a, p2[i] = b;
g[a][b]++, g[b][a]++;
d[a]++, d[b]++;
}
Solve(n);
}
return 0;
}