Posted on 四月 20th, 2008.
对于这道题,只想说三个字:你丫的…
给你一个无向图,要求判断是否存在2-1和2-3的两条路径,使得它们不经过重复的点.拆点,然后重新连边,最大流(2是源,1′和3′连向汇),拆点流量1,原来边流量2(或者更大),看最大流是不是2就行.
这道题其实很容易,只不过题目数据有问题.做之前被告知这道题数组需要开大一些,数据会超出范围.于是开大了数组,不过WA了.
然后发现,无论怎么调都不行.和Nxun的程序对比,几乎一模一样,可就是不对.于是让raulliubo帮我看,他说我的建图和Nxun不太一样.我是把i拆成i和i+n,而他把i拆成i和-i.于是按照他的写,然后AC了.
在Nxun的提示下,加了一句判断:if (x > n) or (y > n) then halt(37);于是RE了.所以发现,原来数据不仅仅是比题目描述的大的问题,点的编号原来还会超过n…巨无语,谁出的数据…
我要说,fxxk you…
另外这道题据rupxup牛说还可以用强联通分量:如果1 2 3在同一个强联通分量里就YES,否则缩点,变成树,然后再做.不过无向图的定向问题怎么办…
p.s.以下是我今天交这道题的记录…我的邮箱快爆掉了.
{ SPOJ 962; Intergalactic Map; IM - sqybi’s code - max flow - dinic}//for my winsty{$Q+R+S+}program im_sqybi; const nn = 50011; mm = 50011; tt = nn + mm * 2 + 3;
var cases, times, n, m, s, t, r, […]
Read Full Post |
Make a Comment ( None so far )
Posted on 四月 12th, 2008.
话说也是攒了好久的题了…今天终于AC了.是CEOI 2003的一道题,SPOJ和POJ上都有.
一道平衡树的题目,用Splay做到了POJ Pascal组第10,SPOJ Pascal组第12.不过Nxun是POJ Pascal组第6,SPOJ Pascal第9…
题目描述么…看我和hrm的这段聊天记录:
hrm 22:51:49什么题啊？Killa.sqybi 22:52:26就是说…一堆屋顶,给出两个端点的坐标,然后任意两个屋顶不相交或者相连Killa.sqybi 22:52:31天上下雨Killa.sqybi 22:52:39问每个屋顶能接到多少雨Killa.sqybi 22:52:44雨会向下流Killa.sqybi 22:52:48就这道题..hrm 22:53:31噢。我退化了hrm 22:53:37不懂为什么用splay了hrm 22:53:45输入是什么啊Killa.sqybi 22:54:30第一行是屋顶数n 接下来n行每行四个数 分别是屋顶左右端点的x y坐标hrm 22:56:11然后呢？每一滴雨的坐标？Killa.sqybi 22:56:39哦..我忘了说每个单位长度落下一滴雨hrm 22:56:57。。。。。hrm 22:57:39那直接用面积不就知道每个屋顶接多少雨了么Killa.sqybi 22:58:02不是..雨会被上面的屋顶挡住..而且会从上面的屋顶比较矮的那边流下来
嗯,就是这样.然后呢,做法就是,从左边开始,用一条扫描线对每个线段的端点进行扫描.每条线段对应三个事件:第一个是左端点,对应线段进入扫描线上的序列;第二个是线段右端点,对应线段离开;第三个是线段比较低的一端,对应的是向下流水.然后,因为两条线段的重叠部分,一条总是高于另一条而不会改变(否则就会相交),所以可以用Splay维护一个线段的序列.最后只要先扫描一遍,同时用一个图记录每条线段的流水情况(流到哪条线段,程序中为了实现方便把边反向),然后进行拓补排序(或者DFS)就可以.
刚才在POJ上AC之后,到SPOJ上死活都TLE.而Nxun在SPOJ上AC的程序,到POJ死活都RE.最后发现了问题,SPOJ是多组数据,而POJ是一组…
{ POJ 1765; SPOJ 86; November Rain - sqybi’s code - Splay - 创建事件点,从左向右扫描,每次维护当前扫描线上所有线段的排序}//for my winstyprogram pku1765_sqybi; const nn = 40000; e = 1e-6;
type rec = record x, p: longint; […]
Read Full Post |
Make a Comment ( None so far )