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, x, y, i, edgeNum: longint;
head, place, dist: array[-nn..nn]of longint;
adj, flow, capa, next: array[-tt..tt]of longint;
q: array[1..nn*2+2]of longint;
procedure addEdge(x, y, z: longint);
begin
inc(edgeNum);
adj[edgeNum] := y;
next[edgeNum] := head[x];
head[x] := edgeNum;
capa[edgeNum] := z;
flow[edgeNum] := 0;
adj[-edgeNum] := x;
next[-edgeNum] := head[y];
head[y] := -edgeNum;
capa[-edgeNum] := 0;
flow[-edgeNum] := 0;
end;
function min(x, y: longint): longint;
begin
if x < y then
min := x
else
min := y;
end;
function bfs: boolean;
var
now, temp, qs, qe: longint;
begin
fillchar(dist, sizeof(dist), 0);
qs := 1;
qe := 1;
q[1] := s;
dist[s] := 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
inc(qe);
q[qe] := adj[temp];
dist[adj[temp]] := dist[now] + 1;
end;
temp := next[temp];
end;
inc(qs);
end;
bfs := dist[t] <> 0;
end;
function dfs(x, d: longint): longint;
var
delta, temp, r: longint;
begin
if x = t then begin
dfs := d;
exit;
end;
temp := place[x];
delta := 0;
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));
flow[temp] := flow[temp] + r;
flow[-temp] := -flow[temp];
delta := delta + r;
if delta = d then break;
end;
temp := next[temp];
end;
place[x] := temp;
dfs := delta;
end;
begin
readln(cases);
for times:=1 to cases do begin
fillchar(head, sizeof(head), 0);
edgeNum := 0;
readln(n, m);
for i:=1 to n do
if i <> 2 then
addEdge(i, -i, 1)
else
addEdge(i, -i, 2);
for i:=1 to m do begin
readln(x, y);
addEdge(-x, y, 2);
addEdge(-y, x, 2);
end;
s := 2;
t := 0;
addEdge(1, t, 1);
addEdge(3, t, 1);
r := 0;
while bfs do begin
place := head;
r := r + dfs(s, 2);
end;
if r = 2 then
writeln(’YES’)
else
writeln(’NO’);
end;
end.
阅读(113 次)