SPOJ 1476 — Maximum Profit (code: PROFIT)
同NOI06最大获利,多组数据.
程序略.
阅读(120 次)
SPOJ 839 — Optimal Marks (code: OPTM)
这道题的解法的确很强大啊,大概意思就是把每个数分为二进制位,然后每一位的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); […]
SPOJ 962 — Intergalactic Map (code: IM)
对于这道题,只想说三个字:你丫的…
给你一个无向图,要求判断是否存在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, […]
SGU 326 — Persepctive
一道很爽的最大流题目.题目中给出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 […]
SGU 185 — Two Shortest
经典的最短路+网络流的题目.
第一行n,m,表示n个点m条边.接下来m行,每行描述一条无向边.x y z表示x,y之间一条无向边,长度为z.要求求出两条没有公共边的最短路.
首先一个SPFA,目的是保留dist数组.然后从最后一个结点开始BFS.对于BFS到某个结点x,如果结点y能够满足dist[y]+table[x, y]=dist[x],则将这条边作为y->x的有向边加入新图中,并将y加入BFS队列(如果y没有被加入过).这样,新图中的边便都是能够构成最短路的边了.接下来对于新图,每条边的容量都看作1,源是1,汇是n,做最大流.得出的最大流就是最短路条数.如果条数少于2,输出无解.如果大于等于2,那么这时我们会获得刚刚计算最大流时的flow数组.从源开始进行DFS,每次只走flow=1的结点,直到走到汇为止,把这条路径上所有flow都变成0.然后再走一次.得到的两条路径输出即可.
然后呢,我的网络流写的是Dinic.于是,我的SPFA+Dinic就华丽的MLE掉了.
谁知道怎么优化内存…开链表不管用,链表会让内存更大.
Update:经过一晚上恶心死人的优化,终于AC了这道题.因为Delphi没有integer类型(Delphi的integer=fpc的longint…而我找不到相当于fpc的integer的类型),于是优化难了很多.最后用上了word,shortint和子界类型,终于AC掉.题目限制1MB内存,我用了1009KB,好险…另外据Wind牛说,可以用最小费用流解.只要加一个源,流2的流量就行.似乎Wind牛还有一个两遍SPFA的算法,未证明正确性.
{ SGU 185; Two shortest - sqybi’s code - 单源最短路 + 最大流 - SPFA + Dinic}//for my winstyprogram sgu185_sqybi; const nn = 400; mm = nn * nn div 2; unable = nn * 10000 + 1;
var n, m, i, qe, qs, r, edgeNum, x, y, z: longint; t: array[1..nn, […]
« Previous Entries