我倒是知道我WA在什么地方了,没有判断度数是否为奇数就开始dfs当做入口。但是我这样不也算是有解吗?
by BIOS @ 2023-06-17 19:42:26
@[BIOS](/user/833124) 我的结果是
$$CIcCvXggwPpl$$
而且比你的字典序小
by Robots75 @ 2023-07-28 19:00:43
@[Robots75](/user/1021365) 那测试点是错的啊,测试点的比你我的答案都大
by BIOS @ 2023-07-28 19:05:59
@[BIOS](/user/833124) 我也是看到这条讨论,发现没判定度
by Robots75 @ 2023-07-28 19:53:28
@[BIOS](/user/833124) 有没有一种可能,你的代码还是有问题
~~当然我的代码也有问题~~,我的目前50tps
```cpp
#include<iostream>
#define N 150
using namespace std;
bool is_input[N],G[N][N],vis[N][N];
int m,now=0,q[N],tot=0,GS[N];
void dfs(int x){
//printf("now dfs %d\n",x);
if(now==m){
for(int i=1;i<=tot;i++)
printf("%c",q[i]);
printf("\n\n\n");
exit(0);
}
for(int i='A';i<='Z';i++){
if(G[x][i]&&!vis[x][i]){
++now;
vis[x][i]=vis[i][x]=1;
q[++tot]=i;
dfs(i);
--tot;
--now;
vis[x][i]=vis[i][x]=0;
}
}
for(int i='a';i<='z';i++){
if(G[x][i]&&!vis[x][i]){
++now;
vis[x][i]=vis[i][x]=1;
q[++tot]=i;
dfs(i);
--tot;
--now;
vis[x][i]=vis[i][x]=0;
}
}
}
int main(){
//freopen("luogu/in.txt","r",stdin);
//freopen("luogu/out.txt","w",stdout);
int x,y;
char a,b;
cin>>m;
for(int i=1;i<=m;i++){
cin>>a>>b;
//printf("%c %c\n",a,b);
is_input[a]=is_input[b]=1;
G[a][b]=G[b][a]=1;
GS[a]++;
GS[b]++;
}
int jsum=0,jflag=0,oflag=0;
for(int i='A';i<='Z';i++){
if(GS[i]%2==1){
if(jflag==0)jflag=i;
jsum++;
}
else if(oflag==0&&GS[i]!=0)oflag=i;
if(jsum>2){
printf("No Solution");
return 0;
}
}
for(int i='A';i<='Z';i++){
if(GS[i]%2==1){
if(jflag==0)jflag=i;
jsum++;
}
else if(oflag==0&&GS[i]!=0)oflag=i;
if(jsum>2){
printf("No Solution");
return 0;
}
}
if(jsum==0){
q[++tot]=oflag;
dfs(oflag);
}
else if(jsum==2){
q[++tot]=jflag;
dfs(jflag);
}
else{
printf("No Solution");
return 0;
}
printf("No Solution");
return 0;
}
```
by Robots75 @ 2023-07-28 20:24:07
@[Robots75](/user/1021365) 我看了一下之前AC的代码,我的代码与AC代码只差了几个符号,就是判断check()那里改成
```
while (!(d[start] & 1))
start++;
```
```
↑这样就可以了
```
by BIOS @ 2023-07-28 22:14:42
@[Robots75](/user/1021365) 从代码含义来看,WA代码只略过了度数为0的情况,AC代码还略过了度数为偶数的情况。
by BIOS @ 2023-07-28 22:17:57
我也最开始踩坑了···但是实际上CvXggwPplcI并不是解,没有经过cC这条边。
无向图里,欧拉图是全部度为偶数,起始点可以选任意;半欧拉图是仅有两个点度为奇数,且这两个点必为起始/终止点。
by 23372k101 @ 2024-01-29 11:19:24