首页 > 其他 > 详细

坑爹的题——bzoj4808

时间：2017-10-09 20:08:31 阅读：207 评论：0 收藏：0 [点我收藏+]

众所周知，马后炮是中国象棋中很厉害的一招必杀技。"马走日字"。本来，如果在要去的方向有别的棋子挡住（俗

称"蹩马腿"），则不允许走过去。为了简化问题，我们不考虑这一点。马跟马显然不能在一起打起来，于是rly在

一天再次借来了许多许多的马在棋盘上摆了起来……但这次，他实在没兴趣算方案数了，所以他只想知道在N×M的

矩形方格中摆马使其互不吃到的情况下的最多个数。但是，有一个很不幸的消息，rly由于玩得太Happy，质量本来

就不好的棋盘被rly弄坏了，不过幸好只是破了其中的一些格子（即不能再放子了），问题还是可以继续解决的。

Input

一行，两个正整数N和M。

接下来N行，每行M个数，要么为0，表示没坏，要么为1，表示坏了。

N<=200,M<=200

一行，输出最多的个数。

2 3
0 1 0
0 1 0

这道题挺简单，二分图最大点独立集即可。然而我调了整整两天。

首先我把match数组打成了bool类型，一小时找到

然后发现每次memset要超时，写了flag，然后Wa了T，T了Wa

然后一直T。。。

最后写了对拍，跑了三小时并没有错，然后一个200*200的全0数据发现得6s中。

网上一份差不多的只要0.6s

然后找各位大佬找了一个晚上，终于发现加边的顺序有问题，首先肯定是靠左上角的比较优，迷之优化。

坑

原文：http://www.cnblogs.com/dancer16/p/7642584.html

踩

(0)

评论一句话评论（0）

分享档案

更多>