icon

2018-11-20

USACO Telecowmunication

to be continued!

link

题目和Pollutant Control 有点类似,但是这次问的是关掉哪些点可以中断起点和终点之间的连接,但还是可以用类似的办法解决。

只要把一个点扩展变成两个点,中间连一条容量为$1$的边,那么删掉这条变相当于删掉了这个点。

why?

  1. 为什么 $cap = 1$
  2. 为什么这么扩展?

写blog真的很好!

因为 max-flow = min-cut

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define per(i, b, a) for (int i = (int)b - 1; i >= (int)a; --i)
#define repv(ele, cont) for (auto &ele : cont)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define eb emplace_back
#define ep emplace
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<ll> vll;
// END OF TEMPLATE

struct Dinic {
  struct Edge {
    int from, to;
    ll cap, flow;
    Edge() {}
    Edge(int f, int t, ll c) : from(f), to(t), cap(c), flow(0) {}
  };
  int N;
  vector<Edge> E;
  vvi g;
  vi d, pt;
  Dinic(int N_) : N(N_), E(0), g(N_), d(N_), pt(N_) {}
  void AddEdge(int u, int v, ll cap) {
    if (u != v) {
      E.eb(u, v, cap);
      g[u].eb(E.size() - 1);
      E.eb(v, u, 0);
      g[v].eb(E.size() - 1);
    }
  }

  bool BFS(int S, int T) {
    queue<int> q({S});
    fill(all(d), N + 1);
    d[S] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      if (u == T) break;
      repv(k, g[u]) {
        Edge &e = E[k];
        if (d[e.to] > d[u] + 1 && e.cap > e.flow) {
          d[e.to] = d[u] + 1;
          q.emplace(e.to);
        }
      }
    }
    return d[T] != N + 1;
  }

  ll DFS(int u, int T, ll flow = -1) {
    if (u == T || flow == 0) return flow;
    for (int &i = pt[u]; i < (int)g[u].size(); ++i) {
      auto &e = E[g[u][i]];
      auto &oe = E[g[u][i] ^ 1];
      if (d[e.to] == d[u] + 1) {
        ll amt = e.cap - e.flow;
        if (flow != -1 && amt > flow) amt = flow;
        if (ll pushed = DFS(e.to, T, amt)) {
          e.flow += pushed;
          oe.flow -= pushed;
          return pushed;
        }
      }
    }
    return 0;
  }

  ll MaxFlow(int S, int T) {
    repv(e, E) { e.flow = 0; }

    ll ret = 0;
    while (BFS(S, T)) {
      fill(all(pt), 0);
      while (ll pushed = DFS(S, T)) { ret += pushed; }
    }
    return ret;
  }

  void setCap(int from, int to, ll cap) {
    repv(i, g[from]) {
      if (E[i].to == to) {
        E[i].cap = cap;
        break;
      }
    }
  }
};

int main() {
#ifndef LOCAL
  freopen("telecow.in", "r", stdin);
  freopen("telecow.out", "w", stdout);
  ios_base::sync_with_stdio(0), cin.tie(0);
#endif
  int n, m, c1, c2;
  cin >> n >> m >> c1 >> c2;
  --c1, --c2;
  Dinic d(2 * n);
  rep(i, 0, m) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    d.AddEdge(a + n, b, 1);
    d.AddEdge(b + n, a, 1);
  }
  rep(i, 0, n) {
    if (i == c1 || i == c2) {
      d.AddEdge(i, i + n, 0x3f3f3f3f);
    } else {
      d.AddEdge(i, i + n, 1);
    }
  }

  int flow = d.MaxFlow(c1, c2);
  cout << flow << '\n';
  if (flow) {
    vi ans;
    rep(i, 0, n) {
      if (i != c1 && i != c2) {
        d.setCap(i, i + n, 0);
        int n_ = d.MaxFlow(c1, c2);
        if (n_ == flow - 1) {
          flow = n_;
          ans.eb(i);
        } else {
          d.setCap(i, i + n, 1);
        }
        if (flow == 0) break;
      }
    }
    rep(i, 0, ans.size()) {
      cout << ans[i] + 1;
      if (i == ans.size() - 1)
        cout << '\n';
      else
        cout << ' ';
    }
  }
  return 0;
}
comments powered by Disqus

search See also