Sol
直接全部數字加起來減一然後除以9就可以了，非常好證正确性。
Code
懶得粘。
構造題。首先考慮直徑最小的構造方案：先看\(n,m\)中有至少一個為奇數：取出奇數那一維的中軸線，然後線上每個點向兩邊一直延伸即可。
每次延長直徑就把邊上的延伸線撇過來。
按照這個邏輯不斷撇就可以了。
如果\(n,m\)均為偶數，要注意無法實作直徑為對角線曼哈頓距離，要特判。
\(Tell\ is\ easy,\ however\ I\ can't\ show\ you\ the\ code.\ Cause\ it's\ too\ hard\ for\ me\ to\ write\ that.\)
首先可以證明：每一條邊最多隻走一次。那麼其實就是花費\(dis(u,v)\)把\(u,v\)聯通起來。
最開始我想的是直接枚舉點集，然後跑\(kruskal\)計算答案取最值，然後發現\(n=2\)的小資料全過，大樣例死活過不了。
然後就發現可能選出來的點集并不隻形成一個最小生成樹，而是一個最小生成森林。是以可以套上一個狀壓DP，把原來計算的答案改成隻計算處在樹中的數的最小值。
這樣每種狀态表示對應二進制位上是否被考慮。設\(g(now)\)表示目前狀态最優答案，\(f(now)\)表示目前狀态全部在同一樹上的答案。那麼答案有
\[g_{now}=\max_{i\&now=i} min(g_i,g_{now\ xor\ i})
\]
\(g(now)\)初始值是\(f(now)\)
加一個記搜，時間複雜度\(O(2^{2n})\)，這樣的話\(n=16\)會被卡，如何優化我也不知道。。。但是對于\(60\)分的優化是很好想的：因為所有點在同一數軸上，是以選擇的邊肯定是一段連續區間才最優，是以狀壓DP狀态枚舉可以改成枚舉區間起點終點，變成\(O(2^n*n^2)\)。
Code（不帶優化）
不會。