P2410 [SDOI2009]最优图像

    • 55通过
    • 485提交
  • 题目提供者 zhangbolin
  • 评测方式 云端评测
  • 标签 SPFA 最短路 各省省选 2009 山东 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小E在好友小W的家中发现一幅神奇的图画,对此颇有兴趣。它可以被看做一个包含N×M个像素的黑白图像,为了方便起见,我们用0表示白色像素,1表示黑色像素。小E认为这幅图画暗藏玄机,因此他记录下了这幅图像中每行、每列的黑色像素数量,以回去慢慢研究其中的奥妙。

    有一天,小W不慎将图画打湿,原本的图像已经很难分辨。他十分着急,于是找来小E,希望共同还原这幅图画。根据打湿后的图画,他们无法确定真正的图像,然而可以推测出每个像素原本是黑色像素的概率Pij%。那么,一个完整的图像的出现概率就可以定义为:

    其中Sij表示在还原后的图像中,像素是白色(0)还是黑色(1)。换句话说,一个完整图像出现概率就等于其所有黑色像素的出现概率之积。显然,图像的黑色像素不能包含概率为0的像素。

    然而,小E对此也无能为力。因此他们找到了会编程的小F,也就是你,请你根据以上信息,告诉他们最有可能是原始图像的答案是什么。

    输入输出格式

    输入格式:

    输入文件image.in的第一行是两个正整数N和M,表示图像大小。

    接下来N行每行包含M个整数,表示每个像素是黑色像素的概率为Pij%。0 ≤ Pij < 100。

    接下来一行有N个非负整数,表示每一行中黑色像素的个数。

    接下来一行有M个非负整数,表示每一列中黑色像素的个数。

    输出格式:

    输出文件image.out包含一个N×M的01矩阵,表示你还原出的图像。输出不包含空格。图像每行、每列中1的个数必须与输入一致,且是所有可能的图像中出现概率最大的一个。输入数据保证至少存在一个可能的图像。如果有多种最优图像,任意输出一种即可。

    输入输出样例

    输入样例#1: 复制
    2 2
    90 10
    20 80
    1 1
    1 1
    
    输出样例#1: 复制
    10
    01
    

    说明

    样例解释:共有两种可能的图像:

    01 10 和 10 01 前者的出现概率是0.1×0.2=0.02,后者的出现概率是0.9×0.8=0.72,故后者是最优图像。

    对于20%的数据,N , M ≤ 5;

    对于100%的数据,N , M ≤ 100。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。