狗挂经

Siil 发表于 2019/12/03 16:49:37
大概思想就是通过二分图来模拟矛盾关系，一边是选，一边是不选，但是仔细想想好像我的图好像是错的，想听听有没有其他人的想法

我觉得没错啊 思路超棒 感觉像是选有几个不同的最大独立集 ？ emmm 然而我并不会二分图

感觉楼主其他答得挺好的就是被第二轮黑了。楼主在哪面的？多久之前？

请问openning 名字是什么啊？

Siil 发表于 2019-12-2 00:15
第二轮的题目可以再详细一点吗？看起来是个match的题目

补充内容 (2019-12-1 08:26):

请问，能再具体解释一下吗~

非常感谢楼主的分享，顺便抱抱楼主

来回答一下……我研究这个东西研究了一晚上- -
第二题，可以通过二分图匹配来找到一个解，左边是每一列，右边是每一个数，列里有数就连边即可
如果要求所有的或者求数目，这个应该是不可能的，这个问题是#P-complete的即使对于每行只有两个数，见这个paper
http://pages.cs.wisc.edu/~jyc/papers/interpolation08.pdf

第一题follow up怎么做啊