#include <iostream> #include <fstream> #include <vector> #include <algorithm> using namespace std; const int MAXN = 3005; int N, K; int w[MAXN][MAXN]; int red[MAXN], blue[MAXN]; int main() { ifstream fin("sub.in"); ofstream fout("sub.out"); fin >> N >> K; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { fin >> w[i][j]; } } // 计算所有可能的红节点和蓝节点的组合 int max_sum = 0; // 枚举红节点数量 r 从1到K-1 for (int r = 1; r <= K - 1; r++) { int b = K - r; // 计算所有红节点的内部边权和 vector<int> red_edges; for (int i = 0; i < N; i++) { int sum = 0; for (int j = 0; j < N; j++) { if (i != j) sum += w[i][j]; } red_edges.push_back(sum); } sort(red_edges.rbegin(), red_edges.rend()); long long red_total = 0; for (int i = 0; i < r; i++) { red_total += red_edges[i]; } red_total /= 2; // 每条边被计算两次 // 计算所有蓝节点的内部边权和 vector<int> blue_edges; for (int i = 0; i < N; i++) { int sum = 0; for (int j = 0; j < N; j++) { if (i != j) sum += (K - w[i][j]); } blue_edges.push_back(sum); } sort(blue_edges.rbegin(), blue_edges.rend()); long long blue_total = 0; for (int i = 0; i < b; i++) { blue_total += blue_edges[i]; } blue_total /= 2; // 每条边被计算两次 // 计算红蓝节点间的边权和 vector<int> cross_red; for (int i = 0; i < N; i++) { int sum = 0; for (int j = 0; j < N; j++) { sum += (K - w[i][j]); } cross_red.push_back(sum); } sort(cross_red.rbegin(), cross_red.rend()); long long cross_red_total = 0; for (int i = 0; i < r; i++) { cross_red_total += cross_red[i]; } vector<int> cross_blue; for (int j = 0; j < N; j++) { int sum = 0; for (int i = 0; i < N; i++) { sum += (K - w[i][j]); } cross_blue.push_back(sum); } sort(cross_blue.rbegin(), cross_blue.rend()); long long cross_blue_total = 0; for (int i = 0; i < b; i++) { cross_blue_total += cross_blue[i]; } long long cross_total = (cross_red_total + cross_blue_total) / 2; // 计算当前组合的总边权和 long long current_sum = red_total + blue_total + cross_total; if (current_sum > max_sum) { max_sum = current_sum; } } fout << max_sum << endl; return 0; }