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 四月 20th, 2008.
一道很爽的最大流题目.题目中给出NBA中一个赛区每个队伍的比赛情况,即:已经赢下的场数,还剩下的场数,赛区内对阵情况,问1号队伍有没有可能拿到赛区第一(或者并列第一,不算小分^_^).
首先先让1号队伍赢下所有的比赛,剩下的队伍输掉所有跨赛区的比赛(某人says:傻子都知道~).建图的时候就是两排点,左边一排代表队伍,右边代表某两个队伍之间的比赛(只要队伍相同,无论多少场都用一个点表示).源到左边点的容量设为那支队伍还可以赢下的最多场数(就是1号队伍赢下的场数减去这个队伍赢下的场数),左边点到右边点建边的条件是,如果第i个队伍和第j个队伍有比赛而且场数为k,比赛对应右边结点的编号为p,那么从i到p和j到p分别连容量为k的边.右边点到汇连边就是那个点代表的两个队伍的比赛场数.然后求最大流,如果右边点到汇都流满的话,就可以找到一组解,输出YES,否则输出NO.
这里需要注意,如果还没有建图的时候,1号队伍赢下的比赛已经不如某一个队伍多,那么1号队伍一定不能拿到第一,这里要特殊判断一下.
{ SGU 326; Perspective - sqybi’s code - max flow - Dinic}//for my winsty{$Q+R+S+}program sgu326_sqybi; const fin = ’sgu326.in’; fout = ’sgu326.out’; nn = 20; tt = nn * nn; mm = nn * nn * 3 + nn;
var m, n, i, j, s, t, tot, r, edgeNum: longint; a, b, c: array[1..nn]of […]
Read Full Post |
Make a Comment ( None so far )