Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
51647 | AK2022071323 | 最优子图 | C++ | 运行超时 | 30 | 2000 MS | 2240 KB | 994 | 2022-07-13 12:22:38 |
#include <cstdio> using namespace std; typedef long long LL; const int N = 510; int n,a[N],b[N]; LL k,sum,minn,maxn,w[N][N]; void dfs(int x,LL s,int c1,int c2) { if(x == n + 1) { if(c1 && c2 && s > maxn) maxn = s; return ; } LL t = s; for(int i = 1; i <= c1; i++) t += w[x][a[i]]; for(int i = 1; i <= c2; i++) t += k - w[x][b[i]]; a[c1 + 1] = x; dfs(x + 1,t,c1 + 1,c2); t = s; for(int i = 1; i <= c1; i++) t += k - w[x][a[i]]; for(int i = 1; i <= c2; i++) t += w[x][b[i]]; b[c2 + 1] = x; dfs(x + 1,t,c1,c2 + 1); } int main() { scanf("%d%lld",&n,&k); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) scanf("%lld",&w[i][j]); if(k == 1) { for(int i = 1; i <= n; i++) { sum = 0; for(int j = 1; j <= n; j++) sum += w[i][j]; minn = minn > sum ? sum : minn; maxn += sum; } maxn = maxn / 2 - minn; } else dfs(1,0,0,0); printf("%lld\n",maxn); return 0; }