已知一个未知其规模的棋盘中有Ｒ个格子，若任意两个格子处于同一行或同一列上，则称这两个格子为互不相容，否则称之为相容的，已知一个棋盘Ｒ个格子两两是相容或不相容的全部信息，编程求出一个相应的棋盘，并要求能包含该棋盘的矩形面积最小。
输入输出要求：
格子间是否相容的信息由一个文本文件提供，该文件第一行是一个数字，代表格子总数Ｒ，其下Ｒ行是一个仅由０、１组成的Ｒ×Ｒ的矩阵，若该矩阵第Ｉ行第Ｉ列为１，表示格子Ｉ与格子Ｊ不相容，否则相容。
输出应显示求得的棋盘和包含该棋盘的最小矩形的长和宽。同时将所求得的棋盘存入一个名为RESULT.TXT的文件中，该文件共有Ｒ行，其中第Ｉ（１≤Ｉ≤Ｒ）行是第Ｉ个格子的坐标，先是横坐标，后是纵坐标，其间以空格分隔。
12 个解决方案
#1
关注！
#2
大家想想,我要结帖了
#3
如果规模不大的话就用搜索解。。。
有没有说R的范围？
有没有说R的范围？
#4
我要分
#5
有点象图的M着色问题的逆问题。
#6
这道题很简单，若干个元素两两相容，那么必然同行/同列。于是我们可以先计算出所有极大的两两相容集合(每个元素最多在两个这样的集合中，不然棋盘不存在）。最多花费O(n^2)时间。
于是每两个相容不同集合最多只有一个公共元素，不然也非法。
我们作一图，以这些相容集合为顶点，两个相容集合之间当且仅当有公共元素的时候连接一条边。
于是这个图的所有的连同分支都必须是二分图，不然也非法。
然后即这些二分图为
G(V11,V12,E1), G(V21,V22,E2),...,G(Vk1,Vk2,Ek)
那么现在的问题就变成
从V11,V12;V21,V22;...;Vk1,Vk2中个选择一个
U1,U2,U3,...,Uk;
假设剩余的集合为
W1,W2,...,Wk
要求
|U1|+|U2|+....+|Uk|同|W1|+|W2|+...+|Wk|最接近，动态规划就可以了。
于是每两个相容不同集合最多只有一个公共元素，不然也非法。
我们作一图，以这些相容集合为顶点，两个相容集合之间当且仅当有公共元素的时候连接一条边。
于是这个图的所有的连同分支都必须是二分图，不然也非法。
然后即这些二分图为
G(V11,V12,E1), G(V21,V22,E2),...,G(Vk1,Vk2,Ek)
那么现在的问题就变成
从V11,V12;V21,V22;...;Vk1,Vk2中个选择一个
U1,U2,U3,...,Uk;
假设剩余的集合为
W1,W2,...,Wk
要求
|U1|+|U2|+....+|Uk|同|W1|+|W2|+...+|Wk|最接近，动态规划就可以了。
#7
最后一步错了，在得到二分图G(V11,V12,E1), G(V21,V22,E2),...,G(Vk1,Vk2,Ek)以后
其中二分图G(Vi1,Vi2,Ei)对应于一个|Vi1|*|Vi2|的矩形，唯一的特例是当某个Vi2是空集的时候，我们认为其包含一个元素。也就是对应|Vi1|*1的矩形。最后我们要将这些矩形放入一个大矩形中，使它们不占用任何举行的同行同列。
也就是
从V11,V12;V21,V22;...;Vk1,Vk2中个选择一个
U1,U2,U3,...,Uk;
假设剩余的集合为
W1,W2,...,Wk
使（|U1|+|U2|+....+|Uk|)*(|W1|+|W2|+...+|Wk|)最小
其中二分图G(Vi1,Vi2,Ei)对应于一个|Vi1|*|Vi2|的矩形，唯一的特例是当某个Vi2是空集的时候，我们认为其包含一个元素。也就是对应|Vi1|*1的矩形。最后我们要将这些矩形放入一个大矩形中，使它们不占用任何举行的同行同列。
也就是
从V11,V12;V21,V22;...;Vk1,Vk2中个选择一个
U1,U2,U3,...,Uk;
假设剩余的集合为
W1,W2,...,Wk
使（|U1|+|U2|+....+|Uk|)*(|W1|+|W2|+...+|Wk|)最小
#8
mathe():
"两两相容，那么必然同行/同列"?
-- 和原来题意正好相反!
"两两相容，那么必然同行/同列"?
-- 和原来题意正好相反!
#9
没有关系，那就两两不相容吧，只是名称的问题。
反正解法是一样的，那就计算出所有两两不相容的极大集合。
反正解法是一样的，那就计算出所有两两不相容的极大集合。
#10
gz
#11
我觉得你贴子的标题是对我们的侮辱----我们是靠能力的分得，不是要你送给的
#12
up
#1
关注！
#2
大家想想,我要结帖了
#3
如果规模不大的话就用搜索解。。。
有没有说R的范围？
有没有说R的范围？
#4
我要分
#5
有点象图的M着色问题的逆问题。
#6
这道题很简单，若干个元素两两相容，那么必然同行/同列。于是我们可以先计算出所有极大的两两相容集合(每个元素最多在两个这样的集合中，不然棋盘不存在）。最多花费O(n^2)时间。
于是每两个相容不同集合最多只有一个公共元素，不然也非法。
我们作一图，以这些相容集合为顶点，两个相容集合之间当且仅当有公共元素的时候连接一条边。
于是这个图的所有的连同分支都必须是二分图，不然也非法。
然后即这些二分图为
G(V11,V12,E1), G(V21,V22,E2),...,G(Vk1,Vk2,Ek)
那么现在的问题就变成
从V11,V12;V21,V22;...;Vk1,Vk2中个选择一个
U1,U2,U3,...,Uk;
假设剩余的集合为
W1,W2,...,Wk
要求
|U1|+|U2|+....+|Uk|同|W1|+|W2|+...+|Wk|最接近，动态规划就可以了。
于是每两个相容不同集合最多只有一个公共元素，不然也非法。
我们作一图，以这些相容集合为顶点，两个相容集合之间当且仅当有公共元素的时候连接一条边。
于是这个图的所有的连同分支都必须是二分图，不然也非法。
然后即这些二分图为
G(V11,V12,E1), G(V21,V22,E2),...,G(Vk1,Vk2,Ek)
那么现在的问题就变成
从V11,V12;V21,V22;...;Vk1,Vk2中个选择一个
U1,U2,U3,...,Uk;
假设剩余的集合为
W1,W2,...,Wk
要求
|U1|+|U2|+....+|Uk|同|W1|+|W2|+...+|Wk|最接近，动态规划就可以了。
#7
最后一步错了，在得到二分图G(V11,V12,E1), G(V21,V22,E2),...,G(Vk1,Vk2,Ek)以后
其中二分图G(Vi1,Vi2,Ei)对应于一个|Vi1|*|Vi2|的矩形，唯一的特例是当某个Vi2是空集的时候，我们认为其包含一个元素。也就是对应|Vi1|*1的矩形。最后我们要将这些矩形放入一个大矩形中，使它们不占用任何举行的同行同列。
也就是
从V11,V12;V21,V22;...;Vk1,Vk2中个选择一个
U1,U2,U3,...,Uk;
假设剩余的集合为
W1,W2,...,Wk
使（|U1|+|U2|+....+|Uk|)*(|W1|+|W2|+...+|Wk|)最小
其中二分图G(Vi1,Vi2,Ei)对应于一个|Vi1|*|Vi2|的矩形，唯一的特例是当某个Vi2是空集的时候，我们认为其包含一个元素。也就是对应|Vi1|*1的矩形。最后我们要将这些矩形放入一个大矩形中，使它们不占用任何举行的同行同列。
也就是
从V11,V12;V21,V22;...;Vk1,Vk2中个选择一个
U1,U2,U3,...,Uk;
假设剩余的集合为
W1,W2,...,Wk
使（|U1|+|U2|+....+|Uk|)*(|W1|+|W2|+...+|Wk|)最小
#8
mathe():
"两两相容，那么必然同行/同列"?
-- 和原来题意正好相反!
"两两相容，那么必然同行/同列"?
-- 和原来题意正好相反!
#9
没有关系，那就两两不相容吧，只是名称的问题。
反正解法是一样的，那就计算出所有两两不相容的极大集合。
反正解法是一样的，那就计算出所有两两不相容的极大集合。
#10
gz
#11
我觉得你贴子的标题是对我们的侮辱----我们是靠能力的分得，不是要你送给的
#12
up