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);
function bfs: boolean;
function dfs(x, d: longint): longint;
procedure getCut(x: longint);
procedure minCut(x: longint);
end;
var
cases, times, n, m, x, y, i, j, t, max: longint;
v1, v2: array[1..nn]of longint;
flag: array[1..nn]of boolean;
g1, g2: TGraph;
function min(x, y: longint): longint;
begin
if x < y then min := x else min := y;
end;
procedure TGraph.addEdge(x, y, z: longint);
begin
inc(edgeNum);
adj[edgeNum] := y;
capa[edgeNum] := z;
flow[edgeNum] := 0;
next[edgeNum] := head[x];
head[x] := edgeNum;
adj[-edgeNum] := x;
capa[-edgeNum] := 0;
flow[-edgeNum] := 0;
next[-edgeNum] := head[y];
head[y] := -edgeNum;
end;
function TGraph.bfs: boolean;
var
qe, qs, now, temp: longint;
begin
fillchar(dist, sizeof(dist), 0);
dist[s] := 1;
q[1] := s;
qs := 1;
qe := 1;
while qs <= qe do begin
now := q[qs];
temp := head[now];
while temp <> 0 do begin
if (dist[adj[temp]] = 0) and (flow[temp] < capa[temp]) then begin
dist[adj[temp]] := dist[now] + 1;
inc(qe);
q[qe] := adj[temp];
end;
temp := next[temp];
end;
inc(qs);
end;
bfs := dist[t] <> 0;
end;
function TGraph.dfs(x, d: longint): longint;
var
temp, delta, r: longint;
begin
if x = t then begin
dfs := d;
exit;
end;
delta := 0;
temp := place[x];
while temp <> 0 do begin
if (dist[adj[temp]] = dist[x] + 1) and (flow[temp] < capa[temp]) then begin
r := dfs(adj[temp], min(capa[temp]-flow[temp], d-delta));
delta := delta + r;
flow[temp] := flow[temp] + r;
flow[-temp] := - flow[temp];
if delta = d then break;
end;
temp := next[temp];
end;
place[x] := temp;
dfs := delta;
end;
procedure TGraph.getCut(x: longint);
var
qs, qe, now, temp: longint;
begin
q[1] := s;
qs := 1;
qe := 1;
fillchar(visit, sizeof(visit), false);
visit[s] := true;
while qs <= qe do begin
now := q[qs];
if (now <> s) and (now <> t) then
v2[now] := v2[now] + x;
temp := head[now];
while temp <> 0 do begin
if (not visit[adj[temp]]) and (temp > 0) and (flow[temp] < capa[temp]) then begin
visit[adj[temp]] := true;
inc(qe);
q[qe] := adj[temp];
end;
temp := next[temp];
end;
inc(qs);
end;
end;
procedure TGraph.minCut(x: longint);
begin
while bfs do begin
place := head;
dfs(s, maxlongint);
end;
getCut(x);
end;
begin
readln(cases);
for times:=1 to cases do begin
readln(n, m);
fillchar(g1.head, sizeof(g1.head), 0);
g1.edgeNum := 0;
for i:=1 to m do begin
readln(x, y);
g1.addEdge(x, y, 1);
g1.addEdge(y, x, 1);
end;
g1.s := 0;
g1.t := n + 1;
readln(t);
fillchar(v1, sizeof(v1), 0);
fillchar(flag, sizeof(flag), false);
max := 0;
for i:=1 to t do begin
readln(x, y);
v1[x] := y;
flag[x] := true;
if y > max then max := y;
end;
fillchar(v2, sizeof(v2), 0);
for i:=1 to 31 do begin
g2 := g1;
x := 1 shl (i - 1);
if x > max then break;
for j:=1 to n do
if flag[j] then
if v1[j] div x mod 2 = 1 then
g2.addEdge(g2.s, j, maxlongint)
else
g2.addEdge(j, g2.t, maxlongint);
g2.minCut(x);
end;
for i:=1 to n do
writeln(v2[i]);
end;
end.
阅读(134 次)