#P2240. ural1676 Mortal Combat

    ID: 1265 传统题 1000ms 128MiB 尝试: 30 已通过: 10 难度: 7 上传者: 标签>CF2300提高+/省选-二分图建模Kuhn 算法交替路Kosaraju 算法全异约束匹配过滤

ural1676 Mortal Combat

题目描述

有 NN 只河蟹和 MM 只羊驼。每只河蟹都必须与一只羊驼交战,每只羊驼最多参加一场。已知每一对参赛者交战时羊驼能否获胜。羊驼要安排所有对战,并在每一场对战中获胜。

对每一对河蟹、羊驼,判断是否存在一种安排,使这两只参赛者交战且所有羊驼获胜。如果根本不存在全胜安排,则每一对都不可能选用。

输入格式

第一行两个整数 N,MN,M(1≤N≤3001\le N\le300,N≤M≤1500N\le M\le1500)。

接下来 NN 行,每行 MM 个连续的二进制字符,组成矩阵 AA。当且仅当第 jj 只羊驼能击败第 ii 只河蟹时,Aij=1A_{ij}=1。

输出格式

输出 NN 行,每行 MM 个连续的二进制字符。如果第 ii 只河蟹与第 jj 只羊驼不能出现在任何全胜安排中,输出矩阵的对应位置为 11,否则为 00。

样例

4 4
1111
1000
1111
1111
1000
0111
1000
1000
4 5
10000
10000
10000
10000
11111
11111
11111
11111

题目来源