前两天做到的题目。
题目描述
给定若干个长度为4的字符串，用空格分隔，判断这些字符串能否排成首尾相连的字符串。字母区分大小写。
若不能，则输出ERROR；
若可以形成首尾相连的圈，则输出CIRCLE；
否则，依次输出排序后的所有字符串。
考虑思路
此题关键在于字符串的首位两个字符，是个典型的欧拉路问题，需要判断能否形成欧拉路、能否形成欧拉回路，若存在欧拉路，需要输出该路径。
将每个字符串抽象为首位字符代表的两个点，两点之间由首字符向尾字符连一条有向边。相同的字符为同一个点。这样构图就完成了。
判断欧拉回路的条件
无向图: 图连通，所有点都是偶数度
有向图: 图连通，所有点出度=入度
混合图: 构造网络流模型：
1. 对所有的无向边随便取个方向，然后计算每个点的｜出度－入度｜，若为奇数，则不存在；
2. 对每个点求 ｜出度－入度｜/2，记为x；
3. 有向边按原图连边，容量为1；无向边 若出度>入度，则与源点相连，否则与汇点相连，容量为x；
4. 若网络流满流，则存在欧拉回路。
判断欧拉通路的条件
无向图: 图连通，所有点都是偶数度(回路) || 只有两个点是奇数度。当所有点是偶数度时欧拉路起点可以是任意点；当有两个奇数度点时起点必须是奇数度点。
有向图: 图连通，所有点出度=入度(回路) || 有一个点入度-出度=1，有一个点出度-入度=1。同样，当所有点出度=入度时任意点可作为起点；而后者必须以出度-入度=1的点做起点，入度-出度=1的点做终点。
具体到本题
先利用并查集判断是否连通；
在连通的情况下，计算点的度，判断是否存在欧拉通路或欧拉回路；
若存在欧拉通路，利用套圈法求解。
注意到这里有个小trick，看题目描述，不能被区分大小写这句突兀的话误导（汗其实自己想当然了。。＝ ＝），题目说的是字符串，可以是任何可见字符，不一定是大小写字母。所以点的数量不只26*2个。
关键代码
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
const int MAXN = 500;
struct Str
{
char str[5];
int next;
bool used;
Str() {next = -1; used = 0;}
}word[1000005];
int word_list[MAXN][MAXN];
char line[4000005];
char *p;
int mat[MAXN][MAXN];
int path[1000005];
int in[MAXN];
int out[MAXN];
int father[MAXN];
bool vis[MAXN];
void find_path_d(int now, int& step)
{
for (int i = MAXN-1; i >= 0; i--)
{
while (mat[now][i])
{
mat[now][i]--;
find_path_d(i, step);
}
}
path[step++] = now;
}
int euclid_path(int start)
{
int ret=0;
memset(path, -1, sizeof(path));
find_path_d(start,ret);
return ret;
}
int Find(int x)
{
while(x!=father[x])
x = father[x];
return x;
}
void Union(int r1,int r2)
{
int a = Find(r1);
int b = Find(r2);
if(a!=b)
father[a] = b;
}
bool check(int a, int b)
{
int r1 = in[a] - out[a];
int r2 = in[b] - out[b];
if((r1==1 && r2==-1) || (r1==-1 && r2==1))
return true;
return false;
}
int solve(int x)
{
int diff = 0;
int odd_a = 0;
int odd_b = 0;
int line = 0;
x = Find(x);
for(int i = 0; i < MAXN; i++)
{
if(vis[i])
{
if(out[i] != in[i])
{
diff++;
if(!odd_a) odd_a = i;
else if(!odd_b) odd_b = i;
else
{
line = 1;
break;
}
}
if(Find(i)!=x)
{
line = 1;
break;
}
}
}
if(line==0 && diff==0)
return 1;
if(line==0 && diff == 2 && check(odd_a,odd_b))
return 2;
return -1;
}
void init()
{
memset(mat, 0, sizeof(mat));
memset(vis, 0, sizeof(vis));
memset(in, 0, sizeof(in));
memset(out, 0, sizeof(out));
for (int i = 0 ; i < MAXN; i++)
father[i] = i;
}
int main()
{
while (gets(line)!=NULL)
{
p = strtok(line, " ");
init();
int num = 0;
bool table[60];
memset(table, 0, sizeof(table));
int x;
int cnt = 0;
while(p)
{
int st, ed;
st = p[0];
ed = p[strlen(p)-1];
if (!table[st])
{
num++;
table[st] = 1;
}
if (!table[ed])
{
num++;
table[ed] = 1;
}
strcpy(word[cnt].str, p);
word[cnt].next = word_list[st][ed];
word[cnt].used = 0;
word_list[st][ed] = cnt++;
p = strtok(NULL, " ");
mat[st][ed] += 1;
in[ed]++;
out[st]++;
vis[st] = vis[ed] = 1;
Union(st, ed);
x = st;
}
int ans = solve(x);
if (ans == 1)
{
puts("CIRCLE");
}
else if (ans == -1)
{
puts("ERROR");
}
else
{
int i;
for (i = 0; i < MAXN; i++)
{
if (out[i]-in[i]==1)
break;
}
int len = euclid_path(i);
for (int i = len-2; i >= 0; i--)
{
int word_id = word_list[path[i+1]][path[i]];
while (word[word_id].used && word[word_id].next!=-1)
{
word_id = word[word_id].next;
}
if (word_id!=-1)
{
word[word_id].used = 1;
printf("%s ", word[word_id].str);
}
}
puts("");
}
}
return 0;
}
|