RUN ID85735483
以下是我的代码:
#include <bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define Rep(i, s, e) for (re int i = s; i <= e; ++i)
#define Dep(i, s, e) for (re int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
typedef long long ll;
const int MAXLOG = 18;
const int NMAX = (1 << MAXLOG) - 1;
il int read() {
int x = 0; bool f = true; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = false; c = getchar();}
while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? x : -x;
}
int getlog(int x) {
int res = 0;
while (x) x >> 1, ++res;
return res;
}
int n, m, k, c[MAXLOG][MAXLOG], cnt[NMAX + 10], dig[NMAX][MAXLOG];
ll f[NMAX + 10][MAXLOG + 1], ans, a[MAXLOG];
int main() {
n = read(), m = read(), k = read();
int nmax = (1 << n) - 1;
Rep(i, 1, n) a[i] = read();
Rep(i, 1, nmax) {
Rep(j, 0, n - 1) {
if (i & (1 << j)) {
dig[i][++cnt[i]] = j;
}
}
}
Rep(i, 1, k) {
int u = read(), v = read();
c[u][v] = max(c[u][v], read());
}
Rep(i, 0, nmax) {
if (cnt[i] > m) continue;
if (cnt[i] == 1) {
Rep(x, 1, n) f[i][x] = a[x];
}
else {
Rep(x, 1, cnt[i]) {
Rep(y, 1, cnt[i]) {
if (x == y) continue;
f[i][dig[i][x] + 1] = max(f[i][dig[i][x] + 1], f[i - (1 << dig[i][x])][dig[i][y] + 1] + a[dig[i][x] + 1] + c[dig[i][y] + 1][dig[i][x] + 1]);
}
}
}
if (cnt[i] == m) {
Rep(j, 1, n) ans = max(ans, f[i][j]);
}
}
printf("%lld", ans);
return 0;
}
这是 WA 的输入数据:
18 2 4
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
18 2 5
7 8 3
1 18 2
6 4 1
正确答案是 6,CF 判定我输出 19,可是我本机上运行的结果是 6 啊,有没有大佬帮帮我 QAQ