QOJ #1814. Kingdoms and Quarantine 题解

Description

有两个王国：A 国（有 $ N_1 $ 个城市）和 B 国（有 $ N_2 $ 个城市），以及 $ M $ 条双向道路，每条道路连接一个来自 A 国的城市和一个来自 B 国的城市，且任意两个城市之间至多有一条道路相连。

A 国的城市编号为 $ 1 $ 到 $ N_1 $，B 国的城市编号为 $ N_1 + 1 $ 到 $ N_1 + N_2 $。道路编号为 $ 1 $ 到 $ M $；第 $ i $ 条道路连接城市 $ a_i $ 和 $ b_i $，其中 $ a_i $ 和 $ b_i $ 满足：$1 \leq a_i \leq N_1$ 且 $N_1 + 1 \leq b_i \leq N_1 + N_2$。

从前，一种危险的病毒在一个王国中出现，因此两位国王决定关闭一些道路。

设 $ D_j $ 表示城市 $ j $ 最初连接的道路数量（即初始度数），$ d_j $ 表示当前仍然开放（未被关闭）的道路数量（即当前度数）。

一条道路 $ x $ 可以被关闭，当且仅当在关闭之前满足以下所有条件：

• 该道路尚未被关闭；
• $ d_{a_x} $ 与 $ D_{b_x} $ 的奇偶性相同（即同为奇数或同为偶数）；
• $ d_{b_x} $ 与 $ D_{a_x} $ 的奇偶性相同。

请找出最多可以关闭多少条道路，并构造一个关闭道路的操作序列，使得关闭的道路数量达到最大值。

$N_1,N_2,M\leq 3000$。

Solution

首先一条边能删的条件看起来很复杂，考虑把条件放到点上做。

容易发现对于一个点 $i$，第一次操作的另一端点 $j$ 需要满足 $D_i=D_j$，第二次操作需要满足 $D_i\neq D_j$ 且 $j$ 也是在第偶数次操作。

那么把 $D_{a_i}=D_{b_i}$ 的边看成红边，其余的边看成蓝边，则对于每个端点需要满足依次删掉：红蓝红蓝红蓝… 这些边。

容易发现这是充要条件。

但是会发现这个条件我们在确定最终删掉的边后还需要确定顺序，不够强。设 $c_i$ 表示与 $i$ 相连的删掉的红边数，$d_i$ 表示与 $i$ 相连的蓝边数，这里大胆猜测对于对于每个点 $i$，只要满足 $d_i\leq c_i\leq d_i+1$ 就一定合法。证明就考虑归纳从后往前做？

设 $E$ 表示最终删掉的边集，那么合法条件为：

$$\forall v,\sum_{i\in E,col_i=B,a_i=v 或 b_i=v}{x_i}\leq\sum_{i\in E,col_i=R,a_i=v 或 b_i=v}{x_i}\leq\sum_{i\in E,col_i=B,a_i=v 或 b_i=v}{x_i}+1$$

设一个偏移量 $s_i$ 表示两种边的差，那么就是：

$$\forall v,\sum_{i\in E,col_i=B,a_i=v 或 b_i=v}{x_i}+s_v=\sum_{i\in E,col_i=R,a_i=v 或 b_i=v}{x_i}$$

其中 $s_i\in [0,1]$。

将所有式子相加可以得到 $\displaystyle\sum_{i=1}^{N_1}{s_i}=\sum_{i=N_1+1}^{N_1+N_2}{s_i}$，这很像二分图网络流的形式，考虑建图跑费用流。

具体地，超级源点 $S$ 向左部点 $v$ 连流量为 $1$，费用为 $0$ 的边；右部点向超级汇点 $T$ 连流量为 $1$，费用为 $0$ 的边。如果第 $i$ 条边是红边，就让 $a_i\to b_i$，流量为 $1$，费用为 $-1$；否则让 $b_i\to a_i$，流量为 $1$，费用为 $-1$。

然后跑最小费用可行流即可。

求出方案后从后往前随便找一个目前能操作的边就是对的，应该也可以归纳证明。

时间复杂度：$O\left((N+M)^3\right)$，这个是费用流的复杂度，跑不满。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 6e3 + 5;

int n, m, k;
int a[kMaxN], b[kMaxN], deg[kMaxN], now[kMaxN], w[kMaxN][kMaxN];
bool vis[kMaxN];

namespace Dinic {
const int kMaxN = 1e4, kMaxM = 1e5 + 5, kInf = 1e9;

struct Node {
  int v, w, c, pre;
} e[kMaxM];

int tot = 1, n, s, t, cost;
int tail[kMaxN], dis[kMaxN], cur[kMaxN];
bool inq[kMaxN], vis[kMaxN];

void adde(int u, int v, int w, int c) { e[++tot] = {v, w, c, tail[u]}, tail[u] = tot; }
void add(int u, int v, int w, int c) { adde(u, v, w, c), adde(v, u, 0, -c); }
void init(int _n, int _s, int _t) {
  std::fill_n(tail, n + 1, 0);
  cost = 0, n = _n, s = _s, t = _t;
}
void clear() {
  std::fill_n(tail, n + 1, 0);
  cost = n = s = t = 0, tot = 1;
}

bool spfa(bool o) {
  std::queue<int> q;
  for (int i = 1; i <= n; ++i) {
    dis[i] = kInf, cur[i] = tail[i], inq[i] = vis[i] = 0;
  }
  q.emplace(s), dis[s] = 0, inq[s] = 1;
  for (; !q.empty();) {
    int u = q.front(); inq[u] = 0, q.pop();
    for (int i = tail[u]; i; i = e[i].pre) {
      int v = e[i].v, w = e[i].w, c = e[i].c;
      if (w && dis[v] > dis[u] + c) {
        dis[v] = dis[u] + c;
        if (!inq[v]) q.emplace(v), inq[v] = 1;
      }
    }
  }
  return dis[t] < (!o ? kInf : 0);
}

int dfs(int u, int lim) {
  if (u == t || !lim) {
    cost += lim * dis[t];
    return lim;
  }
  vis[u] = 1;
  int flow = 0;
  for (int &i = cur[u]; i; i = e[i].pre) {
    int v = e[i].v, w = e[i].w;
    if (!vis[v] && w && dis[v] == dis[u] + e[i].c) {
      int tmp = dfs(v, std::min(w, lim));
      if (!tmp) dis[v] = kInf;
      e[i].w -= tmp, e[i ^ 1].w += tmp;
      lim -= tmp, flow += tmp;
      if (!lim) break;
    }
  }
  vis[u] = 0;
  return flow;
}

std::pair<int, int> maxflow(bool o) {
  int64_t ans = 0;
  for (; spfa(o); ans += dfs(s, kInf)) {}
  return {ans, cost};
}
} // namespace Dinic

namespace No_ok_flow {
const int kMaxN = 1e4, kMaxM = 1e5 + 5, kInf = 1e9;

int n, s, t, flow, cost, d[kMaxN];

void init(int _n) {
  for (int i = 0; i <= n; ++i) d[i] = 0;
  n = _n, s = n + 1, t = n + 2, cost = 0;
  Dinic::clear(), Dinic::init(t, s, t);
}

void add(int u, int v, int l, int r, int c) {
  Dinic::add(u, v, r - l, c), d[u] -= l, d[v] += l, flow += l, cost += l * c, w[u][v] += l;
}

bool solve() {
  int tot = 0;
  for (int i = 1; i <= n; ++i) {
    if (d[i] > 0) Dinic::add(s, i, d[i], 0), tot += d[i];
    else if (d[i] < 0) Dinic::add(i, t, -d[i], 0);
  }
  return tot == Dinic::maxflow(0).first;
}
} // namespace No_ok_flow

namespace Yes_max_flow {
const int kInf = 1e9;

int n, s, t;

void add(int u, int v, int l, int r, int c) {
  No_ok_flow::add(u, v, l, r, c);
}

void init(int _n, int _s, int _t) {
  n = _n, s = _s, t = _t;
  No_ok_flow::init(n), No_ok_flow::add(t, s, 0, kInf, 0);
}

std::pair<int, int> maxflow() {
  if (!No_ok_flow::solve()) return {-1, -1};
  Dinic::s = s, Dinic::t = t;
  auto [flow, cost] = Dinic::maxflow(1);
  // std::cerr << "fuck " << flow << ' ' << cost << '\n';
  return {flow, cost + No_ok_flow::cost};
}
} // namespace Yes_max_flow

namespace Flow {
void init(int _n, int _s, int _t) { Yes_max_flow::init(_n, _s, _t); }
void add(int u, int v, int l, int r, int c) {
  if (c >= 0) Yes_max_flow::add(u, v, l, r, c);
  else Yes_max_flow::add(u, v, r, r, c), Yes_max_flow::add(v, u, 0, r - l, -c);
}
std::pair<int, int> maxflow() { return Yes_max_flow::maxflow(); }
} // namespace Flow

void dickdreamer() {
  std::cin >> n >> m >> k;
  for (int i = 1; i <= k; ++i) std::cin >> a[i] >> b[i], deg[a[i]] ^= 1, deg[b[i]] ^= 1;
  int s = n + m + 1, t = s + 1;
  Flow::init(t, s, t);
  for (int i = 1; i <= n; ++i) Flow::add(s, i, 0, 1, 0);
  for (int i = 1; i <= m; ++i) Flow::add(i + n, t, 0, 1, 0);
  for (int i = 1; i <= k; ++i) {
    if (deg[a[i]] == deg[b[i]]) Flow::add(a[i], b[i], 0, 1, -1);
    else Flow::add(b[i], a[i], 0, 1, -1);
  }
  auto [flow, cost] = Flow::maxflow();
  for (int i = 1; i <= Dinic::n; ++i) {
    for (int eid = Dinic::tail[i]; eid; eid = Dinic::e[eid].pre)
      w[i][Dinic::e[eid].v] += Dinic::e[eid].w;
  }
  for (int i = 1; i <= k; ++i) {
    // if (deg[a[i]] == deg[b[i]]) std::cerr << w[b[i]][a[i]] << '\n';
    // else std::cerr << w[a[i]][b[i]] << '\n';
    if (deg[a[i]] == deg[b[i]]) vis[i] = w[b[i]][a[i]];
    else vis[i] = w[a[i]][b[i]];
    now[a[i]] ^= vis[i], now[b[i]] ^= vis[i];
  }
  std::vector<int> vec;
  for (;;) {
    int id = 0;
    for (int i = 1; i <= k; ++i) {
      if (!vis[i]) continue;
      int o = (deg[a[i]] ^ deg[b[i]] ^ 1);
      if (now[a[i]] == o && now[b[i]] == o) { id = i; break; }
    }
    if (!id) break;
    vec.emplace_back(id), vis[id] = 0, now[a[id]] ^= 1, now[b[id]] ^= 1;
  }
  std::reverse(vec.begin(), vec.end());
  std::cout << vec.size() << '\n';
  for (auto x : vec) std::cout << x << ' ';
  // Dinic::init(t, s, t);
  // for (int i = 1; i <= n; ++i) Dinic::add(s, i, 1, 0);
  // for (int i = 1; i <= m; ++i) Dinic::add(i + n, t, 1, 0);
  // for (int i = 1; i <= k; ++i) {
  //   if (deg[a[i]] == deg[b[i]]) Dinic::add(a[i], b[i], 1, -1);
  //   else Dinic::add(b[i], a[i], 1, -1);
  // }
  // auto [flow, cost] = Dinic::maxflow();
  // std::cout << flow << ' ' << -cost << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}