| 题目名称 | 2059. [ZOJ 1458]牛奶瓶编号 |
|---|---|
| 输入输出 | milkdate.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 mikumikumi
于2015-10-11加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：2， 提交：2， 通过率：100% | ||||
 KZNS |
100 | 0.739 s | 0.29 MiB | C++ |
 mikumikumi |
100 | 0.921 s | 0.29 MiB | C++ |
| 关于 牛奶瓶编号 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
卡在匹配算法的数组没有清空上很久。。。
| ||||
|
搜索+二分图匹配的方法无法在规定时间内通过zoj的数据
貌似需要剪枝 | ||||
【题目描述】
一个被分为N*N个网格的盒子，每一格有可能包含一瓶牛奶或者什么都没有。史密斯先生对每行从左到右记下牛奶的情况，同样对每列从上到下记下牛奶的情况。每一条记录包含N的数字，0表示没有牛奶，1表示有牛奶。不幸的是，2*N条记录的顺序被打乱了，有些数字也模糊不清。
现在史密斯先生请你恢复原来盒子的牛奶情况。
【输入格式】
多组数据，第一行是一个整数N，N<=10代表盒子的规格。之后的2*N行描述了2*N条记录，1代表有牛奶，0代表无牛奶，2代表不确定。
最后一行以0为结尾。
【输出格式】
对于每组数据，如果没有解，输出0。如果有解则输出一组解，并标明每一行，每一列对应那一条记录。
【样例输入】
5 01210 21120 21001 12110 12101 12101 00011 22222 11001 10010 2 00 11 11 01 0
【样例输出】
9 8 6 2 7 4 1 0 1 1 0 10 1 0 0 1 0 1 0 1 1 1 0 3 0 1 0 0 1 5 1 1 1 0 1 0
【提示】
在此键入。
【来源】
在此键入。