TIOJ 1724

, , , , ,

SpaceChem

https://tioj.ck.tp.edu.tw/problems/1724

Description

差點看不懂的題敘。

簡單來說，現在有一張 $N$ 點 $M$ 邊的圖 $G$，第 $i$ 條邊權重是 $C_i$，保證前 $N-1$ 條邊是一棵樹。你希望修改一些邊的權重，使得前 $N-1$ 條邊組成的樹恰好是修改後的圖的一個最小生成樹。第 $i$ 條邊修改成 $D_i$ 的代價是 $|C_i - D_i|$，請輸出最小的代價是多少。

請注意可以修改樹邊也可以修改非樹邊。

$N \leq 100, M \leq 10000$

Solution

如果 $T \subseteq G$ 是一個最小生成樹，則對於每一條不在 $T$ 上的邊 $e = (u, v)$，$e$ 的邊權必須大於等於任何 $\textrm{path}_T(u, v)$ 的邊的邊權，其中 $\textrm{path}_T(u, v)$ 是指 $T$ 上 $u$ 到 $v$ 的簡單路徑。不然的話，就可以把一個樹邊斷掉換成 $e$。不難證明滿足這個條件的話，$T$ 必定也會是一個最小生成樹。

我們可以知道我們只會把樹邊改小、把非樹邊改大。對於一條非樹邊 $e_i = (u, v)$，假設他的權重被改成 $C_i + x_i$，而樹邊 $e_j$ 則改成 $C_j - y_j$，那麼前一段的條件就可以寫成 $C_i + x_i \geq C_j - y_j$，改寫成線性規劃標準式的話就變成

$$
\text{maximize } -\left(\sum x_i + \sum y_i\right)
\text{ s.t. }
\begin{cases}
x_i \geq 0 \\
y_j \geq 0 \\
-x_i - y_j \leq C_i - C_j, \forall {j: e_j\in\textrm{path}_T(e_i)}
\end{cases}
$$

對偶之後變成

$$
\text{minimize } \sum (C_i - C_j) z_{ij}
\text{ s.t. }
\begin{cases}
z_{ij} \geq 0 \\
\sum _ {j: e_j\in \textrm{path} _ T(e_i)} -z_{ij} \geq -1, \forall i \\
\sum _ {i: e_j\in \textrm{path} _ T(e_i)} -z_{ij} \geq -1, \forall j \\
\end{cases}
$$

這個 $\sum z_{ij} \leq 1$ 的形式正好就是二分圖匹配的形式：$z_{ij}$ 表示選了 $(i,j)$ 這條邊，而 $i$ 和 $j$ 的限制分別表示左邊和右邊的頂點的所有鄰邊當中只能選一條。因此本題就歸約到一個二分圖最小權匹配問題，左右部的頂點分別代表非樹邊跟樹邊。

直接建圖的話會有 $N+M$ 個頂點跟 $\mathcal{O}(NM)$ 條邊，在上面跑一般的 min cost flow 的話，流量是 $\mathcal{O}(N)$ 而每次最短路徑需要的時間理論上應該要是 $\mathcal{O}(N^2M)$（$NM$ 條邊並且 bellman ford 要更新 $N$ 輪），總時間應該是 $\mathcal{O}(N^3M)$，因此我認為這樣就過有點誇張。

雖然本題測資直接建圖會過（或者應該說 min cost flow 就是 $\mathcal{O}(會過)$），但我還是寫了倍增法優化建圖。基本上就是在建 flow model 的時候先蓋一個類似樹上倍增法的結構，然後每次一個非樹邊加邊到樹上所有路徑就可以用四個倍增的節點解決。這樣就只有 $\mathcal{O}(M+N\log N)$ 條邊了。可以證明 bellman ford 也至多只要更新 $\mathcal{O}(N\log N)$ 輪，所以複雜度就是妥妥的 $\mathcal{O}(N \cdot N\log N \cdot (M + N\log N))$… 代進去一點都不妥。反正就是過了。用 potential + dijkstra 的 演算法大概可以壓更好。

一個值得注意的點是，我們推出來的式子是「最小權匹配」而不是「最小權完美匹配」，所以在用 min cost max flow 模板求解的時候要小心模板會盡量流滿而讓一些權重正的邊也被選上了。如果是直接建圖的話就直接把那些邊刪掉就好了，而優化建圖則是需要加一些邊或是把 min cost max flow 模板小修改一下來處理。

AC code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef local
#define safe cerr << __LINE__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int cnt = sizeof...(T);
  (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
  cerr << "\e[1;32m[ " << s << " ] = [ ";
  for (int f = 0; L != R; ++L)
    cerr << (f++ ? ", " : "") << *L;
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

using lld = int64_t;

template <typename F, typename C> class MCMF {
  static constexpr F INF_F = numeric_limits<F>::max();
  static constexpr C INF_C = numeric_limits<C>::max();
  struct E { int to, r; F f; C c; };
  vector<vector<E>> g; vector<pair<int, int>> f;
  vector<int> inq; vector<F> up; vector<C> d;
  optional<pair<F, C>> step(int S, int T) {
    queue<int> q;
    for (q.push(S), d[S] = 0, up[S] = INF_F;
        not q.empty(); q.pop()) {
      int u = q.front(); inq[u] = false;
      if (up[u] == 0) continue;
      for (int i = 0; i < int(g[u].size()); ++i) {
        auto e = g[u][i]; int v = e.to;
        if (e.f <= 0 or d[v] <= d[u] + e.c) continue;
        d[v] = d[u] + e.c; f[v] = {u, i};
        up[v] = min(up[u], e.f);
        if (not inq[v]) q.push(v);
        inq[v] = true;
      }
    }
    if (d[T] == INF_C) return nullopt;
    for (int i = T; i != S; i = f[i].first) {
      auto &eg = g[f[i].first][f[i].second];
      eg.f -= up[T]; g[eg.to][eg.r].f += up[T];
    }
    return pair{up[T], d[T]};
  }
public:
  MCMF(int n) : g(n),f(n),inq(n),up(n),d(n,INF_C) {}
  void add_edge(int s, int t, F c, C w) {
    g[s].emplace_back(t, int(g[t].size()), c, w);
    g[t].emplace_back(s, int(g[s].size()) - 1, 0, -w);
  }
  pair<F, C> solve(int a, int b) {
    F c = 0; C w = 0;
    while (auto r = step(a, b)) {
      c += r->first, w += r->first * r->second;
      ranges::fill(inq, false); ranges::fill(d, INF_C);
    }
    return {c, w};
  }
};

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M;
  cin >> N >> M;

  vector<int> c(M);
  vector<pair<int, int>> es;
  vector<vector<pair<int,int>>> g(N);
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;

    if (i < N - 1) {
      g[a].emplace_back(b, i);
      g[b].emplace_back(a, i);
    }
    es.emplace_back(a, b);
    cin >> c[i];
  }

  vector<int> pa(N), pa_edge(N), dep(N);
  auto dfs = [&](auto &&self, int i, int p = -1) -> void {
    for (auto [j, id] : g[i]) if (j != p) {
      pa[j] = i;
      pa_edge[j] = id;
      dep[j] = dep[i] + 1;
      self(self, j, i);
    }
  };
  pa[0] = 0;
  pa_edge[0] = -1;
  dfs(dfs, 0);

  constexpr int inf = 1e9;

  int tot = M;
  constexpr int LG = 15;
  vector<int> sparse_table[LG];
  for (int l = 0; l < LG; l++) {
    sparse_table[l].resize(N);
    for (int i = 0; i < N; i++) {
      sparse_table[l][i] = tot++;
    }
  }

  auto anc = [&](int v, int step) {
    while (step--) {
      v = pa[v];
      if (v == pa[v]) break;
    }
    return v;
  };
  auto get_max = [&](int u, int v) {
    int res = -inf;
    while (u != v) {
      res = max(res, c[pa_edge[u]]);
      u = pa[u];
    }
    return res;
  };

  auto lca = [&](int a, int b) {
    while (a != b) {
      if (dep[a] < dep[b]) swap(a, b);
      a = pa[a];
    }
    return a;
  };

  const int S = tot, T = tot + 1;
  MCMF<int64_t, int64_t> flow(tot + 2);

  for (int i = 0; i < N; i++)
    if (pa_edge[i] != -1)
      flow.add_edge(pa_edge[i], sparse_table[0][i], inf, 0);
  for (int l = 0; l + 1 < LG; l++) {
    for (int i = 0; i < N; i++) {
      int j = anc(i, 1 << l);
      flow.add_edge(sparse_table[l][i], sparse_table[l + 1][i], inf, 0);
      flow.add_edge(sparse_table[l][j], sparse_table[l + 1][i], inf, 0);
    }
  }

  for (int i = N - 1; i < M; i++) {
    auto [a, b] = es[i];
    int l = lca(a, b);

    // int mx = max(get_max(a, l), get_max(b, l));
    // if (mx <= c[i]) continue;

    for (int u : {a, b}) {
      if (u == l) continue;
      const int d = dep[u] - dep[l];
      const int lg = __lg(d);
      const int v = anc(u, d - (1 << lg));
      debug(u+1, v+1, lg);
      // assert(anc(v, 1 << lg) == l && anc(v, (1 << lg) - 1) != l);
      flow.add_edge(sparse_table[lg][u], i, inf, 0);
      flow.add_edge(sparse_table[lg][v], i, inf, 0);
    }
  }

  for (int i = 0; i < N - 1; i++) {
    flow.add_edge(S, i, 1, -c[i]);
    flow.add_edge(i, T, 1, c[i]); // not match anything
  }
  for (int i = N - 1; i < M; i++)
    flow.add_edge(i, T, 1, c[i]);

  auto [_, ans] = flow.solve(S, T);
  cout << -ans << '\n';

  // C_i - x_i <= C_j + y_j
  // x_i >= 0
  // y_j >= 0
  // x_i + y_j >= C_i - C_j
  // minimize \sum x_i + \sum y_j

  // dual ->
  // minimize (C_j - C_i) e_{ij}
  // s.t. \sum _ j e_{ij} <= 1, \sum _ i e_{ij} <= 1
  // e_{ij} >= 0
}

後記

改寫 /about 的時候有感於是去一連串刷了好幾題 TIOJ 的題目。各種焦慮加上冬天很寒冷的憂鬱，不過至少寫 TIOJ 跟寫題解帶給我還有活力的感覺。

最近一個很煩的事情是藍芽耳機用一陣子就會莫名奇妙斷線連不回來，必須關機後再開機（對，不能 reboot）才能修好。懷疑是 kernel 的問題但怎麼樣都找不到哪裡有有用的錯誤訊息。不知道要不要改用 lts kernel。

去玩了一下之前 steam 買的小遊戲們（例如 baba is you 或是 這個），但感覺自己沒有定力玩這些小遊戲太久。這是不是就是所謂的電子…

comments powered by Disqus