PCYCLE - Thám hiểm mê cung
Tác giả: ladpro98
Ngôn ngữ: C++
#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;
}