3336 ACM Underground

Posted on 2010-03-03 15:00 王之昊 阅读(214) 评论(0)  编辑 收藏 引用 所属分类: pku
    题目大意是 alice 从 s 点做火车到 t点,但是想逃票, 路线是由若干条线路组成的,若两条线路相交,那么可以转车,路线上可能有警察,如果警察在交点上,那么你转车他就会检查你的票,不转车他就不会管你 ; 如果警察在线路的其他位置,那么只要你碰到他,他就会检查你。有最多100条线路,3000个警察。问 alice 是否能逃票成功。
    
     关键是建图。 把线路离散化,然后以子线段作为结点。如果直接把警察作为分割点的话,最后的子线段可能很多。在交点处的警察不应该作为分割点,他们只是表示这两条线路不可转车。剩余的在线路上的警察是分割点。
     
     先考虑一条线路,用分割点把它隔开。首先可以明确这些子线段不直接相连。考虑两条线路间的关系。如果这两条线路的交点上有警察,我们可以认为这两条线路直接不相连。
     
     具体实现的第一步是确定哪些是分割点, 哪些不是。可以根据 对于每个警察,他在几条线路上 判断。如果他在0条线路上。不是分割点。如果他在1条线路上,是分割点。如果他在多条线路上,我认为这些线路间不具备直接相连性。
     然后把分割点分到每条线路上去,去把每条线路分割成子线段。并且标明这些子线段不具有直接相连性。
     然后考虑那些虽然相交,但是我们认为他们不直接相连的线路,把它们的子线段标记成不直接相连。
     最后这些子线段的数量小于 n + m。算出剩余的两两子线段的关系。最后求一下连通块即可。
     
 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


posts - 26, comments - 7, trackbacks - 0, articles - 17

Copyright © 王之昊