我臆测了这道题的输入格式==

评测机真快……感人肺腑
神奇地跪了一下：源点的余流=边的容量=INF，然后就压没了……没了……

我去。。。并查集中，将return father(f[k]);改成return f[k] = father(f[k]); 竟然可以快几秒钟。

刚开始看错题写了贪心。。。。

这是一个极为有趣的证明。
嗯，。。刚刚我妈打电话把我批了一顿，大半夜了还不回家。。我先给个简述吧；
易证填数存在贪心规则，Max应和Min在一起。依次排序。[否则存在num>Min,num+Max>Min+Max]
填数应从对角线开始,以S型向对面填充{贪心规则可证Num1+1+Num2<Num1+Num2+n+1,Num1+Num2+2n+1=Num1+n+Num2+n+1}。可以发现式子中的对称性[Right1+Right2=Left1+Left2等价于Right1+Right2+1=Right1-n-1+Right2+n(同时满足Max填充和Min填充)]和层次[S型填充{贪心}]都会表现出来。
最大值出现在中心区域附近，
加之对称性，可得
Ans=Max-(2n+1)(int)/2+Min+n/2=Max+Min+n/2=N*N+N/2+1
介于直接证出来了，所以我就没有按照习惯测试各种算法的效率。但是还是大致说一下：
枚举O(n!)
DP?这。。思路不是很清＝＝想过某种空间爆表的记忆化搜索。
贪心O(n^2)
数学证明O(1)

评测插件呢==

回复 @digital-T :
准确说是“修改位置”的字典序

回复 @cstdio : 没理领会你什么意思。f/m无法确定一定值来计算吧。如果不依序逐次更新f/m的值的话，会出现以下情况：
Ａ＋Ｂ＋Ｃ配件（有序）使得Ｆ／Ｍ最大，而Ｄ虽大于ｆ／ｍ（ｃｏｓｎｔ），但是却比最优值低。

回复 @CH.Genius_King :
没弄明白……能举个例子吗？

因为$a=\frac{ \sum_{i=1}^{n} {Fi}}{ \sum_{i=1}^{n} {Mi}}$
可知，任意可使加速度增大的配件应满足 $\frac{F[i]}{M[i]}> \frac{F}{M}$
否则会对整体产生阻碍作用。因此F[i]/M[i]越大，越优。
得到配件按加速度降序的序列，从最大值开始扫描，若满足上述关系，则加入一次优配件仍可使汽车加速[由于汽车本身F/M决定]，可以发现，每加一次 $\frac{F}{M}$都会增加（前提是满足上式，可以用等比性质证明）。直到不满足为止。

哈哈哈。。dfs按字典序走，输出时按OOX这种走，谁知道是XOO，输出左右顺序一改就对了。。。
再顺便吐槽一下USACO练胆题系列

回复 @CH.Genius_King :
①用一个f/m值更大的配件代替某个配件显然更优，因此选取的是f/m值前若干大的配件
②加入前若干大配件导致的a值变化显然是单峰的，因此O(n)扫描

直接上贪心，竟然对了 求大神给证明

回复 @weizj :
是啊

联赛的时候一直在找规律，心想第一题什么时候这么难了
动规。字符串处理。都试过
现在发现穷举不会超时

果的二分答案题。。。没好好估计上界跪了两次- -

不开O2过掉，开了E一个点，累不爱
使用了插头DP：逐格递推，四进制括号表示法，map判重，更新时生成状态
因为没把map清空跪了一晚上

TMD没说求得的回文数的进制啊！！

依次优化的过程：
1.快速幂+1~n顺序查找(30%)
2.对数优化+1~n顺序查找(70%)
3.对数优化+2分查找(具备单调性)(100%)