#include <iostream> #include <fstream> #include <vector> #include <algorithm> using namespace std; int main() { ifstream fin("sub.in"); ofstream fout("sub.out"); int N, K; fin >> N >> K; // 假设前N/2个节点是红色，后N/2个节点是蓝色 int red_count = N / 2; int blue_count = N - red_count; vector<vector<int>> w(N, vector<int>(N)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { fin >> w[i][j]; } } int max_sum = 0; // 枚举所有可能的红色和蓝色节点数量组合 for (int r = 1; r < K; ++r) { int b = K - r; if (r > red_count || b > blue_count) continue; // 计算每个红色节点的内部边权和外部边权 vector<pair<int, int>> red_nodes; for (int i = 0; i < red_count; ++i) { int inner_sum = 0; int outer_sum = 0; for (int j = 0; j < red_count; ++j) { if (i != j) inner_sum += w[i][j]; } for (int j = red_count; j < N; ++j) { outer_sum += w[i][j]; } red_nodes.emplace_back(-(inner_sum + outer_sum), i); } // 计算每个蓝色节点的内部边权和外部边权 vector<pair<int, int>> blue_nodes; for (int i = red_count; i < N; ++i) { int inner_sum = 0; int outer_sum = 0; for (int j = red_count; j < N; ++j) { if (i != j) inner_sum += w[i][j]; } for (int j = 0; j < red_count; ++j) { outer_sum += w[i][j]; } blue_nodes.emplace_back(-(inner_sum + outer_sum), i); } // 按边权和排序 sort(red_nodes.begin(), red_nodes.end()); sort(blue_nodes.begin(), blue_nodes.end()); // 选择前r个红色节点和前b个蓝色节点 vector<bool> selected(N, false); for (int i = 0; i < r; ++i) { selected[red_nodes[i].second] = true; } for (int i = 0; i < b; ++i) { selected[blue_nodes[i].second] = true; } // 计算选中节点的总边权和 int current_sum = 0; for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { if (selected[i] && selected[j]) { current_sum += w[i][j]; } } } // 更新最大边权和 if (current_sum > max_sum) { max_sum = current_sum; } } fout << max_sum << endl; return 0; }