# 112-1 515507 演算法概論期末上機考題解
## A
和 Homework 1 A 一樣的題目，只是少了要輸出解的步驟。可以使用 Divide & Conquer 或 DP 解決。

:::spoiler Sample solution

#include <iostream>
#include <vector>
using namespace std;

constexpr long long INF = 1'000'000'000'000'000'000LL;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &i : a)
    cin >> i;
  long long ans = -INF, sum = 0;
  int ansl, ansr, curl = 0;
  for (int i = 0; i < n; i++) {
    if (sum + a[i] > ans) {
      ans = sum + a[i];
      ansl = curl + 1;
      ansr = i + 1;
    }
    sum += a[i];
    if (sum <= 0) {
      sum = 0;
      curl = i + 1;
    }
  }
  cout << ans << '\n';
}

:::

## B

Homework 5 B 的類題。使用 Disjoint Set 維護每個 Connected Component，在每個 Connected Component 紀錄他的大小。
則可以發現第一個操作相當於 Union 兩個 set，而第二個操作相當於詢問某個 set 的大小，都是經典的 Disjoint set 操作。

:::spoiler Sample solution

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct DSU {
  int n;
  vector<int> p, size;
  void init(int n_) {
    n = n_;
    p.resize(n);
    size.resize(n);
    for (int i = 0; i < n; i++) {
      p[i] = i;
      size[i] = 1;
    }
  }
  int find(int u) { return p[u] == u ? u : p[u] = find(p[u]); }
  void add_edge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v)
      return;
    if (size[u] > size[v])
      swap(u, v);
    size[v] += size[u];
    p[u] = v;
  }
  int get_size(int u) { return size[find(u)]; }
} dsu;

int main() {
  int n, q;
  cin >> n >> q;
  dsu.init(n);
  while (q--) {
    int type;
    cin >> type;
    if (type == 1) { // add edge
      int u, v;
      cin >> u >> v;
      u--, v--;
      dsu.add_edge(u, v);
    } else if (type == 2) { // get count
      int u;
      cin >> u;
      u--;
      cout << dsu.get_size(u) << '\n';
    }
  }
}

:::

## C

手寫作業題。方法是首先先從一個節點開始找出距離他最遠的那個點，之後再從那個最遠的點找到距離他最遠的點，這個距離就是 Tree Diameter。
找最遠的距離使用 BFS 或 DFS 都可以。

:::spoiler Sample solution

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

void dfs(int u, int p, vector<int> &dist, vector<vector<int>> &G) {
  for (int v : G[u])
    if (v != p) {
      dist[v] = dist[u] + 1;
      dfs(v, u, dist, G);
    }
}

int main() {
  int n;
  cin >> n;
  vector<vector<int>> G(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }
  vector<int> dist(n, -1);
  dist[0] = 0;
  dfs(0, -1, dist, G);
  int v = max_element(dist.begin(), dist.end()) - dist.begin();
  dist = vector<int>(n, -1);
  dist[v] = 0;
  dfs(v, -1, dist, G);
  cout << *max_element(dist.begin(), dist.end()) << '\n';
}

:::

## D

這題會需要用到在 Tree 上做 DP 的概念。

注意到有根樹的每個節點都還是有根樹，這就讓樹可以很好的做 DP 或 Divide and Conquer。
在這題中，我們在樹以任意節點為根以後，令 $dp[u][0/1]$ 代表說以 $u$ 這個節點為根的 subtree，
且 $u$ 不在（或在）independent 時，subtree 的 independent set 最大權重和可以是多少。
我們有以下遞迴式：

$dp[u][0] = \sum_{v \in S_u} \max(dp[v][0], dp[v][1])$
$dp[u][1] = (\sum_{v \in S_u} dp[v][0]) + a_u$

其中 $S_u$ 代表 $u$ 的所有 children 的集合。
邊界條件：當一個節點是 leaf 的時候，有 $dp[u][0] = 0, dp[u][1] = a_u$。

實作上可以在 DFS 遞迴的時候順便算出 DP 值，這是最方便的實作方法。

:::spoiler Sample solution

#include <iostream>
#include <vector>
using namespace std;

void solve(int u, int p, vector<vector<long long>> &dp, vector<int> &a,
           vector<vector<int>> &G) {
  long long sum0 = 0, sum1 = 0;
  for (int v : G[u])
    if (v != p) {
      solve(v, u, dp, a, G);
      sum0 += max(dp[v][0], dp[v][1]);
      sum1 += dp[v][0];
    }
  dp[u][0] = sum0;
  dp[u][1] = sum1 + a[u];
}

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  vector<vector<long long>> dp(n, vector<long long>(2));
  vector<vector<int>> G(n);
  for (int &i : a)
    cin >> i;
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }
  solve(0, -1, dp, a, G);
  cout << max(dp[0][0], dp[0][1]) << '\n';
}

:::

## E

### Type 1

直接使用 Dijkstra Algorithm 求出最短路徑長度即可。注意到需要把距離存在一個 min heap 裡面，才會讓整個演算法達到 $O((n + m) \log n)$ 的時間複雜度。

### Type 2

在使用 Dijkstra Algorithm 求出距離以後，我們只保留那些滿足 $dist[u] + w(u, v) = dist(v)$ 的那些（有向）邊，這些邊是「至少在一條從 $1$ 出發的最短路上」的邊。把這些有向邊建起來以後，則可以發現他是一個有向無環圖 DAG（可以想想看為什麼）。在這個新的 DAG 上，任意一個從 $1$ 出發到 $2$ 的路徑都是一個最短路徑。

所以現在的問題就變成一個在 DAG 上數 path 數量的問題。這是手寫作業的題目，可以使用 Topological Sort + DP 解決。在實作中可以不需要真的做 Topological Sort；可以在做 Dijkstra Algorithm 的時候，順便找出那些邊做 DP。細節可以參考 code。

:::spoiler Sample solution

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
constexpr ll MOD = 1'000'000'007;
constexpr ll MAXD = 1e18;

int main() {
  int n, m, type;
  cin >> n >> m >> type;
  vector<vector<pii>> G(n);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    G[u].emplace_back(v, w);
    G[v].emplace_back(u, w);
  }

  vector<ll> dist(n, MAXD), dp(n, 0);
  priority_queue<pli, vector<pli>, greater<>> pq;
  dist[0] = 0, dp[0] = 1;
  pq.emplace(dist[0], 0);
  while (!pq.empty()) {
    auto [distu, u] = pq.top();
    pq.pop();
    if (dist[u] != distu) {
      continue;
    }
    cerr << u << endl;
    for (auto [v, w] : G[u]) {
      if (dist[v] > dist[u] + w) {
        dist[v] = dist[u] + w;
        dp[v] = dp[u];
        pq.emplace(dist[v], v);
      } else if (dist[v] == dist[u] + w) {
        dp[v] = (dp[v] + dp[u]) % MOD;
      }
    }
  }
  if (type == 1)
    cout << (dist[1] == MAXD ? -1 : dist[1]) << '\n';
  else
    cout << (dist[1] == MAXD ? -1 : dp[1]) << '\n';
}

:::

## F

這個問題又稱 [Maximum-weight Clousre Problem](https://en.wikipedia.org/wiki/Closure_problem)，上課的投影片有，位於倒數幾頁可以去參考。

把所有的關係畫成一個有向圖，每條邊的邊權都是 $\infty$。新建一個源點 $s$ 和一個匯點 $t$。對於每個節點 $v$，如果 $a_v > 0$ 就從 $s$ 連到 $v$，邊權是 $a_v$。否則就從 $v$ 連到 $t$，邊權是 $-a_v$。之後求出從 $s$ 到 $t$ 的 min cut，也就是 max flow。之後答案就是原本所有的正的 $a_v$ 減去 min cut。

這個做法正確的原因，可以參考上課投影片或上面的 wiki 連結。

:::spoiler Sample solution

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

static constexpr int MAXF = 1e9;

struct Dinic {
  struct edge {
    int to, cap, flow, rev;
  };
  static constexpr int MAXN = 102;
  vector<edge> v[MAXN];
  int top[MAXN], deep[MAXN], side[MAXN], s, t;
  void make_edge(int s, int t, int cap) {
    v[s].push_back({t, cap, 0, (int)v[t].size()});
    v[t].push_back({s, 0, 0, (int)v[s].size() - 1});
  }
  int dfs(int a, int flow) {
    if (a == t || !flow)
      return flow;
    for (int &i = top[a]; i < v[a].size(); i++) {
      edge &e = v[a][i];
      if (deep[a] + 1 == deep[e.to] && e.cap - e.flow) {
        int x = dfs(e.to, min(e.cap - e.flow, flow));
        if (x) {
          e.flow += x, v[e.to][e.rev].flow -= x;
          return x;
        }
      }
    }
    deep[a] = -1;
    return 0;
  }
  bool bfs() {
    queue<int> q;
    fill_n(deep, MAXN, 0);
    q.push(s), deep[s] = 1;
    int tmp;
    while (!q.empty()) {
      tmp = q.front(), q.pop();
      for (edge e : v[tmp])
        if (!deep[e.to] && e.cap != e.flow)
          deep[e.to] = deep[tmp] + 1, q.push(e.to);
    }
    return deep[t];
  }
  int max_flow(int _s, int _t) {
    s = _s, t = _t;
    int flow = 0, tflow;
    while (bfs()) {
      fill_n(top, MAXN, 0);
      while ((tflow = dfs(s, MAXF)))
        flow += tflow;
    }
    return flow;
  }
  void reset() {
    fill_n(side, MAXN, 0);
    for (auto &i : v)
      i.clear();
  }
} flow;

int main() {
  int n, m;
  cin >> n >> m;
  int sum = 0;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] > 0) {
      flow.make_edge(n, i, a[i]);
      sum += a[i];
    } else {
      flow.make_edge(i, n + 1, -a[i]);
    }
  }
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    flow.make_edge(x, y, MAXF);
  }
  cout << sum - flow.max_flow(n, n + 1) << '\n';
}

:::