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 longint;
ta, tp: array[1..nn, 1..nn]of longint;
head, place, q, dist: array[0..tt]of longint;
adj, next, flow, capa: array[-mm..mm]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
assign(input, fin);
assign(output, fout);
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);
readln;
for i:=1 to n do read(b[i]);
readln;
for i:=1 to n do begin
for j:=1 to n do begin
read(ta[i, j]);
c[i] := c[i] + ta[i, j];
end;
readln;
end;
for i:=1 to n do
if ta[1, i] <> 0 then begin
dec(c[i], ta[1, i]);
ta[1, i] := 0;
ta[i, 1] := 0;
end;
a[1] := a[1] + b[1];
c[1] := 0;
for i:=2 to n do
if a[1] < a[i] then begin
writeln(’NO’);
halt;
end;
m := 0;
for i:=2 to n do
for j:=2 to n do
if (i > j) and (ta[i, j] <> 0) then begin
inc(m);
tp[i, j] := m;
end;
s := 0;
t := n + m + 1;
tot := 0;
edgeNum := 0;
for i:=2 to n do
addEdge(s, i, a[1]-a[i]);
for i:=2 to n do
for j:=2 to n do
if tp[i, j] <> 0 then begin
addEdge(i, tp[i, j]+n, ta[i, j]);
addEdge(j, tp[i, j]+n, ta[i, j]);
addEdge(tp[i, j]+n, t, ta[i, j]);
tot := tot + ta[i, j];
end;
r := 0;
while bfs do begin
place := head;
r := r + dfs(s, maxlongint);
end;
if r = tot then
writeln(’YES’)
else
writeln(’NO’);
close(input);
close(output);
end.
阅读(147 次)