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); […]