Author: lvvj
Date: 20250823
tag: 深度优先搜索
link: https://www.luogu.com.cn/problem/P1294

题目描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 25, M = 105;
int h[N], e[M], w[M], ne[M], idx;
int n, m, vis[N], ans;

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u, int s) {
    ans = max(ans, s);
    
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (!vis[v]) {
            vis[v] = 1;
            dfs(v, s + w[i]);
            vis[v] = 0;
        }
    }
}

int main() {
    cin >> n >> m;

    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i++) {
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    for (int i = 1; i <= n; i++) {
        vis[i] = 1;
        dfs(i, 0);
        vis[i] = 0;
    }
    cout << ans << endl;
    
    return 0;
}