danihao123's Blog

颓一波式子可以发现答案就是\(ABA^T-CA^T\)。然后发现对于一个\(B\)中的元素\(B_{i, j}\)要对答案做出贡献要求\(A_i\)和\(A_j\)都为1，而\(A_i\)为1会导致答案减去一个\(C_i\)。

因此我们可以分别对\(B\)中元素和\(A\)中元素建点。\(B\)中元素会带来收益，但是要求依赖两个\(A\)中元素。而\(A\)中元素会带来一定的笋丝。这个就已经事很明显的最大权闭合子图力，，，

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
const int maxn = 505;
const int maxno = 500 * 500 + 500 + 5;
const int maxm = 2 * (500 * 500 * 3 + 500 + 5);
int first[maxno];
int next[maxm], to[maxm], flow[maxm], cap[maxm];
int gcnt = 0;
void add_edge(int u, int v, int c) {
  gcnt ++;
  next[gcnt] = first[u]; first[u] = gcnt;
  to[gcnt] = v; cap[gcnt] = c; flow[gcnt] = 0;
}
void ins_edge(int u, int v, int c) {
  add_edge(u, v, c); add_edge(v, u, 0);
}
int rev(int i) {
  if(1 & i) {
    return i + 1;
  } else {
    return i - 1;
  }
}

int d[maxno];
int s, t, num;
bool bfs() {
  static bool vis[maxno];
  std::fill(vis, vis + num + 1, false);
  std::fill(d, d + num + 1, 0);
  std::queue<int> Q; Q.push(s);
  d[s] = 1; vis[s] = true;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(!vis[v] && cap[i] > flow[i]) {
        d[v] = d[u] + 1;
        Q.push(v); vis[v] = true;
      }
    }
  }
  return vis[t];
}
int cur[maxno];
int dfs(int x, int a) {
  if(a == 0 || x == t) return a;
  int ret = 0;
  for(int &i = cur[x]; i; i = next[i]) {
    int v = to[i], f;
    if(d[v] == d[x] + 1 && (f = dfs(v, std::min(a, cap[i] - flow[i]))) > 0) {
      ret += f; a -= f;
      flow[i] += f; flow[rev(i)] -= f;
      if(a == 0) break;
    }
  }
  if(a > 0) d[x] = -1;
  return ret;
}
int dinic() {
  int ret = 0;
  while(bfs()) {
    for(int i = 0; i <= num; i ++) cur[i] = first[i];
    ret += dfs(s, 0x7f7f7f7f);
  }
  return ret;
}

int n;
int main() {
  int ans = 0;
  scanf("%d", &n);
  s = 0, t = n * n + n + 1;
  num = t;
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n; j ++) {
      int u = (i - 1) * n + j; int val; scanf("%d", &val);
      ans += val; ins_edge(s, u, val);
      ins_edge(u, n * n + i, 0x7f7f7f7f);
      ins_edge(u, n * n + j, 0x7f7f7f7f);
    }
  }
  for(int i = 1; i <= n; i ++) {
    int val; scanf("%d", &val);
    ins_edge(n * n + i, t, val);
  }
  ans -= dinic();
  printf("%d\n", ans);
  return 0;
}

建了半天图……搞出来了几个神奇的最小割……

然后发现这TM不就是最简单的最大权闭合子图吗……

首先和正负点权普通的最大权闭合子图一样，然后任意\(d_{i, i}\)去依赖点\(i\)。对于一个\(d_{i, j}(i < j)\)，我们要保证那一天\([i, j]\)全部被吃了，所以说它需要依赖\(d_{i + 1, j}\)和\(d_{i, j - 1}\)。

每种寿司的费用也不难处理，我们把\(mx^2\)和\(cx\)分开考虑。\(mx^2\)单独建点，很显然代号为所有\(x\)都要依赖它。对于\(cx\)，可以视为所有点有一个\(x\)的费用。

然后van了……

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
const int maxn = 5000005;
const int maxm = 5000005;
int first[maxn];
int next[maxm], to[maxm], cap[maxm], flow[maxm];
int gcnt = 0;
void add_edge(int u, int v, int f) {
  gcnt ++;
  next[gcnt] = first[u];
  first[u] = gcnt;
  to[gcnt] = v;
  cap[gcnt] = f;
  flow[gcnt] = 0;
}
int rev(int i) {
  if(1 & i) {
    return i + 1;
  } else {
    return i - 1;
  }
}
void ins_edge(int u, int v, int f) {
  add_edge(u, v, f); add_edge(v, u, 0);
}

int s, t;
int d[maxn];
bool bfs() {
#ifdef LOCAL
  // puts("A new round :");
#endif
  static bool vis[maxn];
  memset(vis, 0, sizeof(vis));
  d[s] = 1; vis[s] = true;
  std::queue<int> Q; Q.push(s);
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(cap[i] > flow[i] && !vis[v]) {
        d[v] = d[u] + 1; vis[v] = true;
#ifdef LOCAL
        // printf("d[%d] : %d\n", v, d[v]);
#endif
        Q.push(v);
      }
    }
  }
  return vis[t];
}
int cur[maxn];
int dfs(int u, int a) {
#ifdef LOCAL
  // printf("State (%d, %d)\n", u, a);
#endif
  if(a == 0 || u == t) return a;
  int fl = 0;
  for(int &i = cur[u]; i; i = next[i]) {
    int v = to[i]; int f;
    if(d[v] == d[u] + 1 && (f = dfs(v, std::min(cap[i] - flow[i], a))) > 0) {
      fl += f; a -= f;
      flow[i] += f; flow[rev(i)] -= f;
      if(a == 0) break;
    }
  }
  if(a > 0) d[u] = -1;
  return fl;
}
int tot;
int dinic() {
  int ans = 0;
  while(bfs()) {
    for(int i = 0; i <= tot; i ++) cur[i] = first[i];
    ans += dfs(s, 0x7fffffff);
  }
  return ans;
}

int ma_p[105], ma_m[1005];
int ma_d[105][105];
int main() {
  tot = 1;
  int n, m; scanf("%d%d", &n, &m);
  int ans = 0;
  s = 0, t = 1;
  for(int i = 1; i <= n; i ++) {
    int a; scanf("%d", &a);
    ma_p[i] = ++ tot;
#ifdef LOCAL
    printf("p[%d] : %d\n", i, tot);
#endif
    if(!ma_m[a]) {
      ma_m[a] = ++ tot;
#ifdef LOCAL
      printf("m[%d] : %d\n", a, tot);
#endif
      ins_edge(tot, 1, m * a * a);
    }
    ins_edge(ma_p[i], 1, a);
    ins_edge(ma_p[i], ma_m[a], 0x7fffffff);
  }
  for(int i = 1; i <= n; i ++) {
    ma_d[i][i] = ++ tot;
    for(int j = i + 1; j <= n; j ++) {
      ma_d[i][j] = ++ tot;
#ifdef LOCAL
      printf("ma_d[%d][%d] : %d\n", i, j, tot);
#endif
    }
  }
  for(int i = 1; i <= n; i ++) {
    int d_i; scanf("%d", &d_i);
    if(d_i >= 0) {
      ans += d_i;
      ins_edge(0, ma_d[i][i], d_i);
    } else {
      ins_edge(ma_d[i][i], 1, -d_i);
    }
    ins_edge(ma_d[i][i], ma_p[i], 0x7fffffff);
    for(int j = i + 1; j <= n; j ++) {
      scanf("%d", &d_i);
      int np = ma_d[i][j];
      if(d_i >= 0) {
        ans += d_i;
        ins_edge(0, np, d_i);
        ins_edge(np, ma_d[i][j - 1], 0x7fffffff);
        ins_edge(np, ma_d[i + 1][j], 0x7fffffff);
      } else {
        ins_edge(np, 1, -d_i);
        ins_edge(np, ma_d[i][j - 1], 0x7fffffff);
        ins_edge(np, ma_d[i + 1][j], 0x7fffffff);
      }
    }
  }
  ans -= dinic();
#ifdef LOCAL
  for(int i = 0; i <= tot; i ++) {
    for(int j = first[i]; j; j = next[j]) {
      if(!(j & 1)) continue;
      int v = to[j];
      if(cap[j] == flow[j]) {
        printf("Edge (%d, %d, %d) deleted.\n", i, v, cap[j]);
      }
    }
  }
#endif
  printf("%d\n", ans);
  return 0;
}