hushaobao/2020hw-code

2020华为软件精英挑战赛-参考代码

initMatch

题目说明

通过金融风控的资金流水分析，可有效识别循环转账，辅助公安挖掘洗钱组织，帮助银行预防信用卡诈骗。基于给定的资金流水，检测并输出指定约束条件的所有循环转账，结果准确，用时最短者胜。

输入信息

输入为包含资金流水的文本文件，每一行代表一次资金交易记录，包含本端账号ID, 对端账号ID, 转账金额，用逗号隔开。  本端账号ID和对端账号ID为一个32位的正整数
 转账金额为一个32位的正整数
 转账记录最多为28万条
 每个账号平均转账记录数< 10
 账号A给账号B最多转账一次
举例如下，其中第一行[1,2,100]表示ID为1的账户给ID为2的账户转账100元：
1,2,100
1,3,100
2,4,90
3,4,50
4,1,95
2,5,95
5,4,90
4,6,30
6,7,29
7,4,28

限制条件

循环转账的路径长度最小为3（包含3）最大为7（包含7），例如账户A给账户B转账，账户B给账户A转账，循环转账的路径长度为2，不满足循环转账条件。

输出信息

输出信息为一个文件，包含如下信息:
 第一行输出：满足限制条件下的循环转账个数
 第二行开始：输出所有满足限制条件的循环转账路径详情。
输出循环转账路径要按照指定排序策略进行排序：总体按照循环转账路径长度升序排序；同一级别的路径长度下循环转账账号ID序列，按照字典序（ID转为无符号整数后）升序排序。
举例如下：
4
1,2,4
1,3,4
4,6,7
1,2,5,4

reMatch

增加条件

转账金额浮动区间约束为[0.2, 3] ：循环转账的前后路径的转账金额浮动，不能小于0.2，不能大于3。 如账户A转给账户B 转X元，账户B转给账户C转Y元， 那么进行循环检测时，要满足0.2 <= Y/X <= 3的条件。

算法

给定有向图G(u,v)，寻找出所有满足长度范围在3-7的闭环

算法步骤：

1、多线程mmap读取数据
2、对数据进行编码，防止过大的数据，构建图的邻接表，然后对其进行排序（为了剪枝以及有序输出）
3、删除出度、入读为0的点
4、DFS反向搜索2层
5、多线程DFS迭代正向搜索。利用4中提前搜索的环进行拼接。
6、多进程写入数据（提交发现多进程快于多线程写入）