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