Topcoder.SRM527.Div1.T2

这场比赛是在半夜……我没参加……

本来打算和两基佬熬夜的，最后关头他们发现寝室有无线网……屁颠屁颠跑回寝室，我住在外面，而且没有笔电，于是被抛弃了……

今天补了一下，275和1050还没来得及看，不过第二题比较巧妙……

给出一些关于一个01矩阵的信息：

1> 01矩阵中的每一行

2> 01矩阵中的每一列

这个矩阵中存在未知元素（未知元素可以使0 or 1）

行的信息按顺序给出，列的信息顺序不确定

求满足以上条件的字典序最小的矩阵

样例：

{"10?"
,"?11"}

{"01"
,"10"
,"1?"}

Returns: {"101", "011" }

这题比较有趣，一开始我觉得这种问题只能用搜的，但是搜的显然会超时……（topcoder就是这点猥琐，30的数据范围，小的要死但是暴搜又会tle……）

其实正解是二分图匹配

实际上我们是要确定一个给定的列的顺序关系

如果给出第i列可以放在矩阵的第j列上，连一条边，最后求完美匹配

但问题在于字典序……

注意到给出的数据范围并不大，可以枚举，一旦出现问号，先把它置为0，发现不存在完美匹配，那么置为1

于是这道傻×题就被搞定了……