# 實作面的小提醒
[toc]
注意，本文假設了讀者了解這些資料結構。
所以如果你不了解這些資料結構，不妨就先了解這些資料結構。
## union find 的重要提醒
### No.1 要注意變數重名
#### 包裝成類
如果你用`struct`包裝成一個類的話，要注意，不能把聯集方法命名為`union`，因為這是C++的關鍵字。可以用`unite`(動詞)代替。
#### 不包裝成類
如果你打算把find, union等方法寫在外面，也要注意不能把find方法取名成`find`，因為這跟`<algorithm>`裡的`std::find`重名。
如果你要做union by rank，也不能把`rank`取成`rank`，因為這跟`<type_traits>`裡的`std::rank`重名。所以要不然加個下劃線什麼的。
所以用struct包裝起來可以省很多麻煩。
### No.2 要操作代表元
要操作代表元
要操作代表元
要操作代表元
十分重要！！！
以下面的[924. Minimize Malware Spread](https://leetcode.com/problems/minimize-malware-spread/description/?envType=problem-list-v2&envId=graph)之題解為例。
union find長這樣：
:::spoiler union find
```cpp=
struct UF {
int root[301], rank[301], infcnt[301], cnt[301];
UF(int n) {
iota(root,root+n,0);
fill(rank,rank+n,0);
fill(infcnt,infcnt+n,0);
fill(cnt,cnt+n,1);
}
void unite(int a,int b) {
a = find(a), b = find(b);
if (a!=b) {
infcnt[a]=infcnt[b]=infcnt[a]+infcnt[b];
cnt[a]=cnt[b]=cnt[a]+cnt[b];
if (rank[a]<rank[b]) {
root[a]=b;
}
else {
root[b]=a;
if (rank[a]==rank[b]) rank[a]++;
}
}
}
int find(int a) {
if (root[a]==a) return a;
return root[a]=find(root[a]);
}
};
```
:::
Solution class是
:::spoiler Solution
```cpp=
class Solution {
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int n = graph.size();
UF uf(n);
for (int i : initial) uf.infcnt[i]++;
for (int i=0;i<n;i++) {
for (int j=i+1;j<n;j++) {
if (graph[i][j]) {
uf.unite(i,j);
}
}
}
sort(initial.begin(),initial.end());
int deccnt = 0;
int ans = initial[0];
for (int i : initial) {
int fi = uf.find(i);
if (uf.infcnt[fi]==1) {
if (uf.cnt[fi]>deccnt) {
ans = i;
deccnt = uf.cnt[fi];
}
}
}
return ans;
}
};
```
:::
所謂“總是操作代表元”說的就是，不要把
```cpp=
int fi = uf.find(i);
if (uf.infcnt[fi]==1) {
if (uf.cnt[fi]>deccnt) {
ans = i;
deccnt = uf.cnt[fi];
}
}
```
寫成
```cpp=
if (uf.infcnt[i]==1) {
if (uf.cnt[i]>deccnt) {
ans = i;
deccnt = uf.cnt[i];
}
}
```
不然你就會莫名其妙的少掉30分鐘時間debug
可別小看這個錯誤，尤其是在你很熟練union find的寫法後，有些進階的題目會要求你紀錄每個集團的邊數，點數，最小最大點等等。記錄這些既然簡單，難就難在一不小心就又寫成以i做索引。所以
>要操作代表元
要操作代表元
要操作代表元
### No.3 沒有必要union by `rank`
如果懶得寫，也可以寫一個randomized union了事，或甚至直接不寫。
因為path compression已經足夠了。
而path compression一定要寫，不然會變成$O(n\log n)$
## Dijkstra/BFS最短路的重要提醒
### using INFO
在多層圖中，有時會有很多狀態，得用`tuple<很多元素>`
這時候比起
```cpp
priority<tuple<int,int,int,int>,vector<tuple<int,int,int,int>>,greater<tuple<int,int,int,int>>> pq;
```
不如
```cpp
using INFO = tuple<int,int,int,int>;
priority<INFO,vector<INFO>,greater<INFO>> pq;
```
### 優化
就bfs而言，只要用`bool been`就可以保證優化
就dijstra而言，要用
```cpp
ll been[N];
memset(been,0x3f,sizeof(been));
```
而且，還需要這兩個優化，不然會超時。
```cpp=
while (!pq.empty()) {
auto [dist,node] = pq.top();
pq.pop();
if (dist > been[node]) continue; // opti 1
for (auto [next,weight] : G[node]) {
ll ndist = dist + weight;
if (ndist >= been[next]) continue;// opti 2
been[next] = ndist;
pq.emplace(next,ll);
}
}
```
這兩個優化不影響正確性，而極大的影響速度。
對於優化一，不能改寫成
`if (dist != been[node]) continue;`
比方說，就[1631. Path With Minimum Effort](https://leetcode.com/problems/path-with-minimum-effort/description/)而言，你需要把
```cpp=
int dir[] = {0,1,0,-1,0};
using da = tuple<int,int,int>;
class Solution {
public:
vector<vector<int>> hei;
vector<vector<int>> been;
int n,m;
int unvis = 1e8;
int dijkstra() {
been.assign(n,vector<int>(m,unvis));
priority_queue<da,vector<da>,greater<da>> que;
que.emplace(0,0,0);
been[0][0] = true;
while (!que.empty()) {
auto [dcurr,i,j] = que.top();
que.pop();
if (dcurr > been[i][j]) continue; // 這一行改成>=才能ＡＣ
if (i == n-1 && j == m-1) return dcurr;
for (int d=0;d<4;d++) {
int inext = i + dir[d], jnext = j + dir[d+1];
if (inext == -1 || inext == n || jnext == -1 || jnext == m)
continue;
int dnext = max(abs(hei[inext][jnext]-hei[i][j]),dcurr);
if (dnext >= been[inext][jnext]) continue;
been[inext][jnext] = dnext;
que.emplace(dnext,inext,jnext);
}
}
return been[n-1][m-1];
}
int minimumEffortPath(vector<vector<int>>& hei) {
n = hei.size();
m = hei[0].size();
this->hei = hei;
return dijkstra();
}
};
```
但是，對於典型的Dijkstra，卻可以用`!=`，很奇妙。 >_<
## 實作鏈式前向星的重要提醒
### 初始化
每次開始建圖前，都要記得初始化`cnt=0`還要`memset(head,-1,sizeof(head))`
不然容易陷入無窮迴圈。
這還算是一個好抓的bug，但是下面這一個
### 無向圖建圖開二倍空間
知道的人都知道，對於無向圖，每次要連接`u`, `v`時，
要call兩次加邊程式：
```cpp!
add_edge(u,v);
add_edge(v,u);
```
這是因為鏈式前向星本質上是為有向圖服務的。
但是不知道的人就不知道，在這種情況下，你的`edges`要開
題目給出的兩倍空間，因為每一個無向邊都 corresponds to 兩個有向邊。
千萬要注意！！！否則就會：
經驗告訴我，這是最容易被忘記的注意事項，而且一但忘記了也很危險。因為sample case給出的邊數都不會大，就更難抓出這種讀取越界的問題了。
## 競賽時的心態問題
1. 在 submit 之前，一定不要眼幹忘了刪掉 debug cout.
2. 隨時注意自己在寫什麼。比方說，應該做到除了由粗心造成的以外再無 CE。這是為了避免浪費時間。
4. 讀題要讀好。是 < 還是 <=? 範圍是多少？ subarray 可不可以非空？要不要用 `long long`?
5. 面對較難題時，先考慮好**所有情況**再開始動手敲算法，或至少要有同等自信。當然不能苛求每次都一次過，但三思而後行仍是一個好習慣。
6. 真的沒有想法的話，先考慮用小數字試試看，舉一些例，或是先寫出暴力解，再作修改。
7. query 能離線就離線、答案能二分就二分。能 $O(n\log n)$ 的事，就不要 $O(n)$。(但是在練習時不能這樣！)
Sign in with Wallet
Connect another wallet