HUAWUE CodeCraft2020

华为云2020软件精英挑战赛开源代码，京津冀东北赛区小问号的女朋友，初赛第9名，复赛A榜第10名，B榜无成绩。

程序清单

初赛、复赛最快以及最鲁棒的版本。

基本思路

建图

建图的数据结构最初使用邻接表的形式，采用**vector套娃**的形式，但是由于vector数组套娃的话，访问速度较慢；后来采用**静态数组**的方法，访问速度较vector套娃有所提升，但是静态数组又受到出入度影响很大，可能会出现内存溢出的情况；最后综合考虑，采用**前向星型**数据结构作为图的最终形式，前向星的边在内存中紧密排布，访问速度较vector套娃快，且不受图的出入度的影响，所需要的空间为 n * sizeof(Edge)。其中，n 为边的数量， 也就是转账记录。

读入

mmap读入。

找环

​ 双向DFS找环算法：先根据反向图反向DFS找3层，对可能成环的点进行标记，在前向DFS中，根据反向DFS的标记进行剪枝；反向DFS过程中，将反向三层的路径存下来，前向DFS过程中，可以进一步剪枝。

trick：

1. 尽量避免不必要的内存访问。

2. 使用拓扑排序进行预处理。

3. 能用uint8/bool数组绝不用u32/int数组，这可能是因为u32/int数组占用空间大，cache中存在的几率更小，从而导致更多的cache miss；

4. 内存对齐，在定义边的数据结构时，需要注意内存对齐问题

   struct Node {
       u32_t to;
       u32_t amount;
       Node() {
           to = 0;
           amount = 0;
       }
       // 升序排序函数
       bool operator<(const Node& node) const { return to < node.to; }
   };

   比

   struct Node {
       u32_t to;
       u64_t amount;
       Node() {
           to = 0;
           amount = 0;
       }
       // 升序排序函数
       bool operator<(const Node& node) const { return to < node.to; }
   };

   要快。

5. 为了提高效率，尽可能压缩数据类型的字节数，类似我们的标志位，从int到char等，这可以提高程序效率，但是同时会牺牲一些可扩展性。

6. DFS过程中的if-continue的判断次序很重要，对于更有可能导致continue的分支应该放在更前面。我们实验时候，会首先判断是否成环，该点是否访问过，然后在判断金额的限制条件；我认为，因为路径标志命中率不高，路径是否重复等判断会提升很多，可以避免后续操作。

7. 多线程负载均衡使用(%4)方式。

8. 为了提高程序效率，将DFS递归转为迭代，递归改成switch形式。

9. 由于数组有序程度较高，使用插入排序来提高排序效率（比赛快结束的时候想到的trick，还没尝试）

输出

​ 由于是竞速比赛，在使用多线程的时候，如果使用线程锁，会对程序的性能有所影响，所以结果存储的数据结构如下：

vector<vector<u32_t>> ans_[THREADNUM][8]; //四个线程，每一个线程的结果存储在vector<Path> [8]中

​ 找环结束后，无需同步处理，在写入处理的时候，只需要去对应内存中取路径使用mmap +memcpy进行写入即可。

总结

​ 代码地址：https://github.com/zhyhy/HUAWUE-CodeCraft2020

​ 非科班，之前一直没有写过这么多C++代码，疫情原因，搞了快两个月，从学习C++的常用stl，学习图论中常用的数据结构和算法，学习linux系统重用指令，对C++内存的认识也有了更深的认识。

​ 能得到这个成绩也很开心，和队友一起每天早上起来就连麦优化代码，一直搞到凌晨，每天看着程序越跑越快，感觉很开心，本次比赛收获也很多。

​ 复赛B榜没有成绩，B榜临时改需求，7环改成8环，转账金额从32位无符号改为float型，我们找环部分的可读性和扩展性较强，主要死在了float数据上。

​ 复赛前一天，我们已经考虑到了复赛当天会改环的长度，我们的双向DFS在设计的时候，就考虑到程序的鲁棒性，比赛当天15分钟就将改好了找8环的程序部分。

1.  采用`long long`存储金额*100后的数值，转换时没有定位到出错点，一个临时变量的类型未改变，在这花费了大量时间；
2.  没有意识到`.x`与`0.xx`乘100倍后的差别；
3.  处理第二个问题时被`\r\n`坑了一把；