## Editorial for VM 08 Bài 20 - Mê cung

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const fi='';
fo='';
maxn=210;
oo=1000000000;
var n,m,s,sum:longint;
a,b:array[1..maxn,1..maxn] of longint;
re,f:array[1..maxn*maxn] of longint;

procedure rf;
var i,x,y:longint;
begin
for x:=1 to n do
for y:=1 to n do
a[x,y]:=-oo;
for i:=1 to m do
begin
a[y,x]:=a[x,y];
sum:=sum+a[x,y];
end;
b:=a;
end;

procedure work;
var i,pos,min:longint;
begin
min:=oo+oo;
for i:=2 to m+1 do
begin
f[i]:=f[i-1]+b[re[i],re[i-1]];
if f[i]<min then
begin
min:=f[i];
pos:=i;
end;
end;
if pos=m+1 then pos:=1;
for i:=pos to m do write(re[i],' ');
for i:=1 to pos do write(re[i],' ');
end;

procedure try(i,x:longint);
var y,t:longint;
begin
if (i>m+1) and (re[m+1]=re[1]) then
begin
work;
close(input); close(output);
halt;
end;
for y:=1 to n do
if a[x,y]<>-oo then
begin
re[i]:=y; t:=a[x,y];
a[x,y]:=-oo; a[y,x]:=-oo;
try(i+1,y);
a[y,x]:=t; a[x,y]:=t;
end;
end;

procedure pr;
var i:longint;
begin
if sum<0 then writeln(-1)
else
begin
re[1]:=1;
try(2,1);
writeln(-1);
end;
end;

begin
assign(input,fi); reset(input);
assign(output,fo); rewrite(output);
rf;
pr;
close(input); close(output);
end.


#include <bits/stdc++.h>
const int N = 201;
const int oo = 1000000000;
using namespace std;
int a[N][N], n, m, d, res[N*N], Q[N*N], F[N*N], deg[N];

bool ok(int pos) {
if (d != m+1) return false;
for(int i=1; i<=n; i++)
if (deg[i] & 1) return false;
int sum = 0;
for(int i=pos; i<d; i++) {
sum += a[res[i]][res[i+1]];
if (sum < 0) return false;
}
for(int i=1; i<pos; i++) {
sum += a[res[i]][res[i+1]];
if (sum < 0) return false;
}
return true;
}

int main()
{
//freopen("PCYCLE.in", "r", stdin);
scanf("%d %d\n", &n, &m);
int i, u, v, c;
for(i=1; i<=m; i++) {
scanf("%d %d %d\n", &u, &v, &c);
a[u][v] = c; a[v][u] = c;
deg[u]++; deg[v]++;
}
int top = 1; Q[1] = 1;
while (top) {
u = Q[top];
for(v=1; v<=n; v++) {
top++;Q[top] = v; break;
}
}
if (u == Q[top]) {
d++;res[d] = u;
top--;
}
}
//for(i=1; i<=d; i++) printf("%d ", res[i]);
int low = oo, start; F[1] = 0;
for(i=2; i<=d; i++) {
F[i] = F[i-1] + a[res[i]][res[i-1]];
if (F[i] < low) {
low = F[i]; start = i;
}
}
if (!ok(start)) printf("-1");
else {
for(i=start; i<=d; i++) printf("%d ", res[i]);
for(i=2; i<=start; i++) printf("%d ", res[i]);
}
return 0;
}


#### Code mẫu của RR

{\$R+,Q+}
PROGRAM PCYCLE;
CONST
FINP='';
FOUT='';
maxn=202;
maxm=20002;
VAR
c:array[0..maxn,0..maxn] of longint;
x:array[1..maxn,1..maxn] of longint;
total:array[1..maxm+1] of longint;
deg,xet:array[1..maxn] of longint;
e,s:array[1..maxm+1] of longint;
start,n,m:longint;
var
f:text;
i,u,v:longint;
begin
assign(f,FINP); reset(f);
for i:=1 to m do
begin
c[v,u]:=c[u,v];
x[u,v]:=1; x[v,u]:=1;
inc(deg[u]); inc(deg[v]);
end;
close(f);
end;
function ktlt:boolean;
var
i:longint;
procedure DFS(u:longint);
var
v:longint;
begin
xet[u]:=1;
for v:=1 to n do
if (x[u,v]=1) and (xet[v]=0) then DFS(v);
end;
begin
DFS(1);
ktlt:=false;
for i:=1 to n do
if xet[i]=0 then exit;
ktlt:=true;
end;
function ktctE:boolean;
var
i:longint;
begin
ktctE:=false;
for i:=1 to n do
if deg[i] mod 2<>0 then exit;
ktctE:=true;
end;
procedure writeOutput(k:longint);
var
f:text;
i,j:longint;
begin
assign(f,FOUT); rewrite(f);
if k=0 then begin writeln(f,-1); close(f); halt; end;
j:=start;
for i:=1 to m+1 do
begin
write(f,e[j],' ');
inc(j);
if j=m+1 then j:=1;
end;
close(f);
end;
procedure EulerCycle;
var
top,u,i,sl:longint;
begin
top:=1; s[1]:=n;
sl:=0;
while top>0 do
begin
u:=s[top];
i:=1;
while (i<=n) and (x[u,i]=0) do inc(i);
if i<=n then
begin
inc(top);
s[top]:=i;
x[u,i]:=0; x[i,u]:=0;
end
else
begin
inc(sl);
e[sl]:=u;
dec(top);
end;
end;
end;
procedure process;
var
i:longint;
begin
for i:=2 to m+1 do
total[i]:=total[i-1]+c[e[i-1],e[i]];
start:=1;
for i:=2 to m+1 do
if total[i]<total[start] then start:=i;
if start=m+1 then start:=1;
end;
function ktok:boolean;
var
i,j:longint;
t:longint;
begin
ktok:=false;
t:=0; j:=start;
for i:=1 to m+1 do
begin
t:=t+c[e[j],e[j+1]];
if t<0 then exit;
inc(j);
if j=m+1 then j:=1;
end;
ktok:=true;
end;
BEGIN
if not ktlt then writeOutput(0);
if not ktctE then writeOutput(0);
EulerCycle;
process;
if not ktok then writeOutput(0);
writeOutput(1);
END.