ec
解法1: BitDP
ハミルトン閉路と同様に， 状態 \(\,(s,v)\,\) の 2つ を持って遷移． ここで，\(s \in 2^{N}\) は訪れた頂点の集合， \(v \in s\) は最後に訪れた頂点．
試験中はこの方針で考えていた． しかし，\(s\) しか状態に持っていなかったため WA. 例を作ることで，間違いを納得しやすかった． Star 型の tree を作って確認した．
例を作るのは，ソースコードを眺めるよりも早く解決する場合も多い． 急がば回れとも言える． 間違いを特定しやすい例を構築する能力は重要． 極端すぎず，暗算が出来る例． また，WA になりそうな場所のあたりがついていれば， それに合わせた例も構築しやすい．
解法2: DFS
訪れた頂点を記録しながら DFS. 実装も少なく，ミスしにくいので試験本番向き．
実装での注意は，DFS から帰るときに， 訪れた DFS で今見ていた頂点について， 訪れたという目印をリセットすること．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
// BitDP
int main() {
ll n,m;
cin >> n >> m;
vvll cost(n, vll(n, -INFL));
ll tot = 0;
rep(i,m){
ll a,b,c; cin >> a >> b >> c;
--a, --b;
cost[a][b] = c;
cost[b][a] = c;
tot += c;
}
ll ans = -INFL;
rep(i,n){
vvll dp(1LL<<n, vll(n, -INFL));
dp[1LL<<i][i] = 0;
rep(s,(1LL<<n)) rep(cu,n) if(s >> cu & 1){
rep(ne, n) if(!(s >> ne & 1)){
ll t = s | (1LL << ne);
assert(t != s);
chmax(dp[t][ne], dp[s][cu] + cost[cu][ne]);
}
}
rep(s,(1LL<<n)) rep(ne,n) if(s >> ne & 1){
chmax(ans, dp[s][ne]);
}
}
cout << ans << endl;
return 0;
}
int main() {
ll n,m;
cin >> n >> m;
vvll cost(n, vll(n, -INFL));
rep(i,m){
ll a,b,c; cin >> a >> b >> c;
--a,--b;
cost[a][b] = c;
cost[b][a] = c;
}
ll ans = -INFL;
vll vis(n);
auto dfs = [&](auto dfs, ll cu, ll dis = 0) -> void {
if(vis[cu]) return;
vis[cu] = true;
chmax(ans, dis);
rep(ne,n) if(cost[cu][ne] > 0){
dfs(dfs, ne, dis+cost[cu][ne]);
}
vis[cu] = false;
};
rep(i,n){
vis = vll(n);
dfs(dfs,i);
}
cout << ans << endl;
return 0;
}
