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
     read(n,m);
     for x:=1 to n do
         for y:=1 to n do
             a[x,y]:=-oo;
     for i:=1 to m do
     begin
          read(x,y,a[x,y]);
          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.

Code mẫu của ladpro98

#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 Link[N][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);
        Link[u][v] = true; Link[v][u] = true;
        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++) {
            if (Link[u][v]) {
                Link[u][v] = false; Link[v][u] = false;
                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;
procedure readInput;
var
  f:text;
  i,u,v:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n,m);
  for i:=1 to m do
    begin
      read(f,u,v,c[u,v]);
      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
  readInput;
  if not ktlt then writeOutput(0);
  if not ktctE then writeOutput(0);
  EulerCycle;
  process;
  if not ktok then writeOutput(0);
  writeOutput(1);
END.