P6906 [ICPC2015 WF] Catering

· · 题解

XIX. P6906 [ICPC2015 WF] Catering

比较简单的网络流。

拆点限制每个点只能经过一次。in_i \to out_i 连容量 1，容量下界 1，权值 0 的边；out_i\to in_j(i < j) 连容量 1，权值 w(i, j) 的边；in_1\to out_1 连容量 k，权值 0 的边。out_i\to T 连容量 1，权值 0 的边。

我们发现直接流 in_1\to T 会出错，因为并不一定需要满流。因此，考虑从 1 到 k 枚举最优流量，每次添加 in_1\to out_1 容量 1，权值 0 的边，将任意时刻最小费用取 \min 即可。时间复杂度是 n 次有源汇上下界费用流。

避免上下界网络流的方法：我们知道 in_i\to out_i 的流量恰为 1 且无权，不妨将其权值设为一个绝对值小于两倍边权的负数，如 -10 ^ 7，那么最小费用方案中每条 in_i\to out_i 流量必为 1，将求得最小值加上 10 ^ 7 n 即可。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using ll = long long;
using uint = unsigned int;
using lll = __int128;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned long long;
inline ll read() {
  ll x = 0, sgn = 0;
  char s = getchar();
  while(!isdigit(s)) sgn |= s == '-', s = getchar();
  while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
  return sgn ? -x : x;
}
inline void print(int x) {
  if(x < 0) return putchar('-'), print(-x);
  if(x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
bool Mbe;
constexpr int N = 200 + 5;
constexpr int M = 1e4 + 5;
constexpr int inf = 1e7;
struct flow {
  int cnt = 1, hd[N], nxt[M << 1], to[M << 1], limit[M << 1], cst[M << 1];
  void add(int u, int v, int w, int c) {
    nxt[++cnt] = hd[u], hd[u] = cnt, to[cnt] = v, limit[cnt] = w, cst[cnt] = c;
    nxt[++cnt] = hd[v], hd[v] = cnt, to[cnt] = u, limit[cnt] = 0, cst[cnt] = -c;
  }
  int in[N], dis[N], fr[N];
  int mincost(int S, int T) {
    int cost = 0;
    while(1) {
      queue<int> q;
      memset(dis, 0x3f, sizeof(dis));
      dis[S] = 0, q.push(S);
      while(!q.empty()) {
        int t = q.front();
        q.pop(), in[t] = 0;
        for(int i = hd[t]; i; i = nxt[i]) {
          int it = to[i], d = dis[t] + cst[i];
          if(limit[i] && d < dis[it]) {
            dis[it] = d, fr[it] = i;
            if(!in[it]) q.push(it), in[it] = 1;
          }
        }
      }
      if(dis[T] > 1e9) return cost;
      int fl = 1064;
      for(int i = T; i != S; i = to[fr[i] ^ 1]) fl = min(fl, limit[fr[i]]);
      for(int i = T; i != S; i = to[fr[i] ^ 1]) limit[fr[i]] -= fl, limit[fr[i] ^ 1] += fl;
      cost += fl * dis[T];
    }
  }
} g;
int n, k;
bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  cin >> n >> k;
  int T = n * 2 + 2;
  for(int i = 0; i < n; i++)
    for(int j = i + 1; j <= n; j++)
      g.add(i * 2 + 1, j * 2, 1, read());
  for(int i = 1; i <= n; i++) g.add(i * 2, i * 2 + 1, 1, -inf), g.add(i * 2 + 1, T, 1, 0);
  int ans = 1e9, cur = 0;
  for(int i = 1; i <= k; i++) {
    g.add(0, 1, 1, 0);
    ans = min(ans, cur += g.mincost(0, T));
  }
  cout << ans + inf * n << endl;
  cerr << TIME << " ms\n";
  return 0;
}
/*
2022/9/25
author: Alex_Wei
start coding at 7:52
finish debugging at 8:15
*/