Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
51628 | AK2022071311 | 最优子图 | C++ | 运行超时 | 30 | 2000 MS | 1244 KB | 1102 | 2022-07-13 12:19:47 |
#include<iostream> #include<list> #include<vector> #include<string> #include<algorithm> #include<cstdio> using namespace std; inline int read(){ int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - 48; ch = getchar();} return x * f; } const int N = 505; int w[N][N], n, k, ans; bool b[N]; int val(int u, int v){ if(b[u] ^ b[v]) return k - w[u][v]; return w[u][v]; } void dfs(int pos){ if(pos == n + 1){ int k = 0; for(int i = 1; i <= n; i++) if(b[i]) k++; if(k == 0 || k == n) return; int sum = 0; for(int i = 1; i < n; i++) for(int j = i + 1; j <= n; j++) sum += val(i, j); ans = max(ans, sum); // for(int i = 1; i <= n; i++) // cout << b[i] << " "; // cout << sum << endl; return; } dfs(pos + 1); b[pos] = 1; dfs(pos + 1); b[pos] = 0; } int main(){ n = read(), k = read(); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) w[i][j] = read(); dfs(1); printf("%d", ans); return 0; }