传送门
由于Arena进不去所以代码就没写了,反正这种题重在思维吧。
Description
构造一个二分图使得其完美匹配数量为K(K<=1000000000),要求两边点数相同且都<=20,边数<=120,允许重边。
Solution
这场出题人是鏼大神,我是看cf上的blog,感觉自己语言表达能力较弱,干脆就当做个翻译好了QAQ
如果没有红色的边,那么整张图完美匹配数为0。现在,我们尝试在点k与点A之间加一条边,我们会发现完美匹配的数量增加了3k。所以,我们可以根据K的三进制表示来加边。最多会有4×20条黑边和2×20 条红边。