啊啊啊只会做水题了……

很显然是最小割吧……长得很像最大权闭合子图，但又不一样的。

那么就把最大权闭合子图中的无穷边（我称之为违约边）的费用改成租用的费用。这样一来，如果选了计划（不割计划）还不购买机器（割去机器），那就只能支付租金了（割违约边）。

这其实也算是一种套路了吧？觉得以前见过很多次但是有很多叫法……

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <algorithm>
#include <queue>
const int maxn = 200005;
const int maxm = 2000005;
const int maxe = maxm << 2;
int n, m;
int first[maxn];
int next[maxe], to[maxe], flow[maxe], cap[maxe];
int gcnt = 0;
inline void add_edge(int u, int v, int f) {
  gcnt ++;
  next[gcnt] = first[u];
  first[u] = gcnt;
  to[gcnt] = v;
  flow[gcnt] = 0; cap[gcnt] = f;
}
inline int rev(int i) {
  return (((i - 1) ^ 1) + 1);
}
inline void ins_edge(int u, int v, int f) {
  add_edge(u, v, f);
  add_edge(v, u, 0);
}
 
int d[maxn];
int s, t, tot;
inline bool bfs() {
  static bool vis[maxn];
  std::fill(vis, vis + 1 + tot, false);
  std::fill(d, d + 1 + tot, 0);
  std::queue<int> Q;
  Q.push(s); vis[s] = true; d[s] = 1;
  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; vis[v] = true;
        Q.push(v);
      }
    }
  }
  return vis[t];
}
int cur[maxn];
int dfs(int x, int a) {
  if(a == 0 || x == t) return a;
  int ans = 0;
  for(int &i = cur[x]; i; i = next[i]) {
    int v = to[i];
    int f;
    if(d[v] == d[x] + 1 && (f = dfs(v, std::min(a, cap[i] - flow[i]))) > 0) {
      ans += f; a -= f;
      flow[i] += f; flow[rev(i)] -= f;
      if(a == 0) break;
    }
  }
  if(a > 0) d[x] = -1;
  return ans;
}
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 main() {
  int n, m; scanf("%d%d", &n, &m);
  s = 0; t = tot = n + m + 1;
  int ans = 0;
  for(int i = 1; i <= n; i ++) {
    int w, p; scanf("%d%d", &w, &p);
    ins_edge(s, i, w); ans += w;
    for(int j = 1; j <= p; j ++) {
      int id, co; scanf("%d%d", &id, &co);
      ins_edge(i, id + n, co);
    }
  }
  for(int i = n + 1; i <= n + m; i ++) {
    int co; scanf("%d", &co);
    ins_edge(i, t, co);
  }
  printf("%d\n", ans - dinic());
  return 0;
}

• 相关文章
• 全局相关文章