[Blog] [Docs] [Code] [Slides] [About]

BZOJ 1001 - 狼抓兔子

网络流

2020-03-26 16:37 CST

Problem

选择权值和最小的边的组合,切断左上角到右下角的所有路径。

很明显就是最小割,然后开始打半天Dinic模板……

Solution

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;

class Edge {
public:
  int to, rev;
  int flow, cap;
  /* Edge() = delete; */
  Edge(int to, int rev, int flow, int cap)
    : to(to), rev(rev), flow(flow), cap(cap) {}
};

class Graph {
private:
  int N;
  vector<int> lev;
  vector<int> cnt;
  vector<int> pos;
  vector< vector<Edge> > adj;

public:
  /* Graph() = delete; */
  explicit Graph(int N): N(N) {
    lev.resize(N, 0);
    cnt.resize(N, 0);
    pos.resize(N, 0);
    adj.resize(N, vector<Edge>());
  }
  void addEdge(int from, int to, int cap) {
    Edge e1(to, cnt[to], 0, cap);
    Edge e2(from, cnt[from], 0, cap); // directed ? 0 : cap
    adj[from].push_back(e1);
    adj[to].push_back(e2);
    ++cnt[from], ++cnt[to];
  }
  bool bfs(int s, int t) {
    for (int i = 0; i < N; ++i) lev[i] = -1;
    lev[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int from = q.front();
      q.pop();
      for (int i = 0; i < cnt[from]; ++i) {
        Edge &e = adj[from][i];
        if (lev[e.to] == -1 and e.flow < e.cap) {
          lev[e.to] = lev[from] + 1;
          q.push(e.to);
        }
      }
    }
    return lev[t] != -1;
  }
  int augment(int cur, int flow, int t) {
    if (cur == t) return flow;
    for ( ; pos[cur] < cnt[cur]; ++pos[cur]) {
      Edge &e = adj[cur][pos[cur]];
      if (lev[e.to] == lev[cur] + 1 and e.flow < e.cap) {
        int delta = augment(e.to, min(flow, e.cap - e.flow), t);
        if (delta > 0) {
          e.flow += delta;
          adj[e.to][e.rev].flow -= delta;
          return delta;
        }
      }
    }
    return 0;
  }
  int dinic(int s, int t) {
    if (s == t) return -1;
    int ans = 0, delta = 0;
    while (bfs(s, t)) {
      for (int i = 0; i < N; ++i) pos[i] = 0;
      while ((delta = augment(s, INF, t)) != 0) {
        ans += delta;
      }
    }
    return ans;
  }
};

int main() {
  int n = 0, m = 0;
  int c = 0;
  scanf("%d%d", &n, &m);
  Graph g(n * m);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m - 1; ++j) {
      scanf("%d", &c);
      g.addEdge(i * m + j, i * m + j + 1, c);
    }
  }
  for (int i = 0; i < n - 1; ++i) {
    for (int j = 0; j < m; ++j) {
      scanf("%d", &c);
      g.addEdge(i * m + j, (i + 1) * m + j, c);
    }
  }
  for (int i = 0; i < n - 1; ++i) {
    for (int j = 0; j < m - 1; ++j) {
      scanf("%d", &c);
      g.addEdge(i * m + j, (i + 1) * m + j + 1, c);
    }
  }
  printf("%d\n", g.dinic(0, n * m - 1));
  return 0;
}

我吐了,这OJ连C++0X都没有………

1001

<EOF>