Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
51647 AK2022071323 最优子图 C++ 运行超时 30 2000 MS 2240 KB 994 2022-07-13 12:22:38

Tests(6/20):


#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; }


测评信息: