Moon Jam's Blog

博觀而約取，厚積而薄發

高中畢業老人的小小回憶錄

🗓️ 比賽日期：2022/03/03 ~ 2022/03/06

前言

一個由多個站點連接而成的網絡裡，每對站點之間都有一定的數據傳輸限制 (單向)。現在你需要計算從網絡的入口（ \(s\) ）到出口（ \(t\) ）之間，數據可以同時傳輸的最大速度是多少。
如下圖，從 \(s\) 到 \(t\) 的最大傳輸速度為 2，最大速度會被路徑上最大傳輸流量所限制，因爲從 \(s\) 到 \(t\) 勢必通過路線 \(v1\rightarrow v2\) ，故這張圖的最大流量為 2。

flowchart LR
s --10--> v1 --2--> v3 --13--> v4 --11--> t

而下面這個圖的最大流量為 19，下文提供一種可能的傳輸方式：

flowchart LR
s --10--> v1
s --17--> v2
v1 --7--> v3 --11--> t
v2 --9--> v4 --16--> t
v1 --6--> v4

• 傳輸 7： \(s\rightarrow v1\rightarrow v3\rightarrow t\)
• 傳輸 3： \(s\rightarrow v1 \rightarrow v4 \rightarrow t\) (因為 \(s\rightarrow v1\) 最多只能傳輸 10 因此在前一次傳輸 7 之後，接下來就只能傳輸 3 了)
• 傳輸 9： \(s \rightarrow v2 \rightarrow v4 \rightarrow t\)
• 7+3+9=19

上述這樣的圖叫做 Network Flow (網路流)，在這樣的圖上尋找這種最大流的想法還可以運用在最小割 (後文會再解釋)、最多不重複路徑、二分圖最大匹配、二分圖最小頂點覆蓋等圖論問題。

CSES Graph Algorithms

CSES Graph Algorithms 的 AC 程式碼

前言

高中最後一次考試，想說要有個善終，也怕自己一不小心被當了，很認真讀了兩三天久久沒碰的化學，讀的時候常常想要找那種超大的表簡單說每一種烴類、官能基的性質、反應，可能就像是一些程式語法的 cheat sheet，能夠在學過之後，重新看到就能馬上回想起來，才不用每次寫題目都要翻講義好久，可惜沒有找到類似的東西，就只好自己做一個了。

前言

為什麼叫做 Functional，顧名思義，他是一個多對一的圖（各個點出度皆為 1），如下表所示：

flowchart LR
1 --> 3
2 --> 4
3 --> 1
4 --> 6
5 --> 9
6 --> 3
7 --> 2
8 --> 1
9 --> 6
10 -->8

這邊就整理了一些常見的題型，以及解題的方法。

前言

常常想要畫一些圖表但總是要去用其他的工具畫完然後再把圖片貼上，這樣很麻煩，所以這邊就來介紹一下怎麼在 NexT 中畫出漂亮的圖表

前言

雖然這題的答案就是 cout << 1;，但因為我隊友不知道怎麼證明，所以就了這篇文章。

CSES Dynamic Programming

CSES Dynamic Programming 的 AC 程式碼

CSES Range Queries

CSES Range Queries 的 AC 程式碼