2117 . 殿壬與最大流
TopCoder
Tags
Description
殿壬是個天才兒童，他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲，而現在要講的，是殿壬出生後七十一個月二十二天大的故事。
殿壬這個時候已經精通各式演算法了，其中圖上的最大流問題尤其令他著迷。而在這一天，殿壬的朋友來找殿壬玩，作為天才兒童，他們決定來較量一番，比誰能比較快回答出以某兩點為源點以及匯點的最大流為多少。
遊戲的形式是這樣子的：兩人各準備了 $Q$ 個問題，每個問題都是 $(s_i, t_i)$ 這樣的形式，代表詢問以 $s_i$ 為源點、 $t_i$ 為匯點的最大流。兩人出完問題以後交換題目，誰先正確作答完全部題目的人就獲勝了！
殿壬回憶起了最大流的定義（以下以 $V$ 代表點集、 $E$ 代表邊集、邊為有向邊，亦即 $(u, v) \neq (v, u)$ ）：
對於每條邊 $(u, v) \in E$ ，令 $c(u, v)$ 為這條邊的容量，且令 $S$ 為源點， $T$ 為匯點。一個合法的流是一個函數 $f: E \to \mathbb{R}^ {+}$ 滿足 $f(u, v) \leq c(u, v), \forall (u, v) \in E$ 且對於所有 $v \in V \setminus \{ S, T \}$ ， $\displaystyle\sum_{(u, v) \in E}{f(u, v)} = \sum_{(v, u) \in E}{f(v, u)}$ 必須成立，亦即對於非源非匯的節點們，流入的流量必須等於流出的流量。一個合法的流 $f$ 的流量 $|f|$ 定義為 $\displaystyle\sum_{(S, u) \in E}{f(S, u)}$ 。一張圖上的最大流為在所有可能的流中，最大的 $|f|$ 。
殿壬還知道，如果要把以上的定義套用到無向圖上的話，只要將每條連接 $u, v$ 的無向邊看做是一條從 $u$ 到 $v$ 的有向邊以及一條 $v$ 到 $u$ 的有向邊即可。
不過要玩這個遊戲必須要有一張圖，於是殿壬又在家裡尋找了許久，終於找到了祖傳的 $N$ 點 $N$ 邊的連通無向圖，其中這張圖上的每條無向邊的容量皆為 $1$ ！於是兩人開始了比賽，可是殿壬的朋友不像殿壬那樣的擅長最大流的計算，因此請你幫幫他，回答殿壬所出的 $Q$ 道問題。
（關於網路流更詳細的說明請見下方的 Hints ，若仍不理解可以參考 day4 的網路流講義）
Input Format
輸入第一行有一個正整數 $N$ ，代表圖的頂點數量。
接著 $N$ 行每行有兩個正整數 $u_i, v_i$ ，代表節點 $u_i$ 以及 $v_i$ 之間有一條邊。
接著輸入一個正整數 $Q$ ，代表詢問的數量。
接著 $Q$ 行每一行有兩個正整數 $s_i, t_i$ ，代表詢問以 $s_i$ 為源點、 $t_i$ 為匯點的最大流。
- $2 \leq N \leq 2 \times 10^ 5$
- $1 \leq Q \leq 2 \times 10^ 5$
- $1 \leq u_i, v_i \leq N, u_i \neq v_i$
- $1 \leq s_i, t_i \leq N, s_i \neq t_i$
Output Format
對於每筆詢問，輸出一行代表該詢問的答案。
Sample Input 1
1 2
2 3
3 1
1
1 3
Sample Output 1
Hints
在上圖中，節點 $1$ 到節點 $3$ 的最大流為 $3$ ，其中 $f(1, 3) = 1$ 、 $f(1, 2) = 2$ 、 $f(2, 4) = 3$ 、 $f(3, 4) = 2$ 、 $f(2, 3) = 0$ 。可以驗證這種流法滿足每條邊的容量以及每個非源非匯點的流入與流出限制，並且沒有其他流法可以達到更大的總流量。
上述流法圖示如下：
注意到上圖並非範例測試資料，也不滿足題目的條件。
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~33 | 1 |