Archive for 四月, 2008
Posted on 四月 21st, 2008.
这道题的解法的确很强大啊,大概意思就是把每个数分为二进制位,然后每一位的xor都不互相影响而且每一位只有0和1两种状态.然后可以求最小割来解题.具体解法见Amber在2007年的论文,请点开页面下载.这道题在论文的第13页,这里不再赘述.
做题时不知怎么心血来潮把31写成30,于是WA了几次(开始还因为数组开小TLE了几次,怎么SPOJ不报RE…).还有就是给出的点的权值有可能是0,所以不能通过判断v1数组来判断某个点是不是给出的(这也是我的flag数组的作用).这道题排在Pascal第11.
SPOJ已经2.8分了,1295名…
{SPOJ 839; Optimal Marks; OPTM- sqybi’s code- 按照二进制位建图,最小切割最大流- Dinic}program optm_sqybi; const nn = 500; mm = 3000; tt = nn + mm * 2;
type TGraph = object edgeNum, s, t: longint; adj, next, capa, flow: array[-tt..tt]of longint; visit: array[0..nn+1]of boolean; head, place, dist: array[0..nn+1]of longint; q: array[1..nn+2]of longint; procedure addEdge(x, y, z: longint); […]
Read Full Post |
Make a Comment ( None so far )
Posted on 四月 21st, 2008.
同上题,无代码无题解.SGU水题怎么这么多…
to raulliubo:这道题本来不想做的,不过你的程序实在是太xx了…
阅读(132 次)
Read Full Post |
Make a Comment ( None so far )
Posted on 四月 21st, 2008.
不贴代码,不写题解.自己去看题.只想说:SGU怎么会有这么RP的题目…
阅读(100 次)
Read Full Post |
Make a Comment ( None so far )
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 )
« Previous Entries Next Entries »