最大团

简单起见，直接用mask遍历所有情况也就是从0-2n。 时间复杂度是O(2n·n2) #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<unsigned long long> adj(n, 0); vector<vector<long long>> w(n, vector<long long>(n, 0)); for (int i = 0; i < m; i++) { int u, v; long long ww; cin >> u >> v >> ww; --u; --v; if (u == v) continue; adj[u] |= (1ULL << v); adj[v] |= (1ULL << u); w[u][v] = w[v][u] = max(w[u][v], ww); // 重边取最大，想累加就改这里 } long long bestW = LLONG_MIN; unsigned long long bestMask = 0; //最优2进制团 unsigned long long ALL = (n == 64 ? ~0ULL : ((1ULL << n) - 1)); for (unsigned long long mask = 1; mask <= ALL; mask++) { bool ok = true; //ok标记当前mask是不是团，如果不是团继续下一个mask(也就是mask++) for (int i = 0; i < n; i++) { if (mask & (1ULL << i)) //i在当前mask里面 { unsigned long long others = mask & ~(1ULL << i); //others是i之外的mask之内的点 if (others & ~adj[i]) //如果这些i之外的mask之内的点与i之间存在没有边的情况就说明不是团,ok=false { ok = false; break; } } } if (!ok) continue; //如果不能成团直接排除这个mask long long sum = 0; for (int i = 0; i < n; i++) if (mask & (1ULL << i)) //i点在mask内 for (int j = i + 1; j < n; j++) if (mask & (1ULL << j)) //j点也在musk内 sum += w[i][j]; //直接加上w[i][j]因为就算没有边权值也是0不影响结果 if (sum > bestW) { bestW = sum; bestMask = mask; } //记录最大团 } cout << bestW << "\n"; bool first = true; for (int i = 0; i < n; i++) if (bestMask & (1ULL << i)) { if (!first) cout << ' '; first = false; //这两行是输出格式化的，美观 cout << (i + 1); //下标转换为序号 } cout << "\n"; return 0; }