• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ3436 – ACM Computer Factory

    ACM-POJ EXP 287阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    老实说,我完全看不懂题目在说什么= =。。。Orz

    不过还是简单概括下:

    有N台机器,每台机器有P部分,每部分都有各自的输入、输出规格,因此一台机器有P个输入规格,P个输出规格。每台机器有2*P+1种参数去描述:
      第一个参数Q: 该机器的容量
      接下来P个参数S: 该机器各部分的输入规格
      接下来P个参数D: 该机器各部分的输出规格

    其中输入规格有三种情况:0, 1, 2
      0:该部分不能存在
      1:该部分必须保留
      2:该部分可有可无

    输出规格有2种情况:0, 1
      0:该部分不存在
      1:该部分存在

    至于这条题要我做什么,我完全不理解= =

    不过通过对样例的输入输出的剖析,再加之前人总结出来的一些不清不楚的见解,我能够详尽地分析这题的模型O(∩_∩)O哈哈~


    注意:本题只可以有一次输入,一次输出,还有Sample I/O这段英文不用输入输出

    Sample input:

    P N (N台机器,每台机器有P部分)

    接着输入N行,其实每行都是一个结点的信息

    每一行的格式为 一个Q P个S P个D

    其中Q为当前结点的容量,S都是当前结点的输入规格,D都是输出规格

    Sample output:

    第一行的两个数字分别表示:最大流的值,流量发生变化的边数M(和s还有t关联的边不在其内,那些不属于原有的边,是附加边)

    接下来有M行,每一行都有三个数字,A B W

    A B为流量发生变化的边的端点,W为流量的变化值(每条边初始流量为0,最终流量就是找到最大流时的流量)

    若图不连通,则输出0 0


    解题思路

    最大流问题

    首先构造图

    添加两个超级源s, 超级汇t
      ① 如果某个节点(i)的输入部分不含1,则添加一条s->i路径,容量为Qi;
      ② 如果某个节点(j)输出全为1,则添加一条j->t路径,容量为Qj;
      ③ 如果节点i的输出与j的输入不存在冲突(输出与输入对应位置的和不能为1),则添加一条i->j的路径,容量为min(Qi, Qj).

    PS:输出与输入对应位置的和不能为1,就是说组合为可以为00,11, 21或20,但不能是01


    折磨了我3天的题。。。网上的前辈都推荐拆点做,但是我没有用拆点(感觉拆点很麻烦)

    这道题我用了三种方法去做,但是结果却差强人意:
      ① 【BFS+标号法+不拆点】 成功AC
      ② 【BFS+压入重标法+不拆点】(WA,不知道错哪里了,找不到反例)
      ③ 【BFS+压入重标法+模拟拆点】(WA,不知道错哪里了,找不到反例)

    AC的程序我贴下面,后两个WA的代码我贴在AC代码下面,希望有达人帮我查出哪里出错了。。。无限感激


    方法一:BFS+标号法+不拆点 (AC)

    转载请注明:EXP 技术分享博客 » POJ3436 – ACM Computer Factory

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址