我就是来复习Dinic算法的，仅10天不写，我已经退化成写一遍+调试需要接近一个小时了，当然其中不乏在网上乱逛的时间…
赞成从S源点连一条单向边，反对向T汇点连一条单向边，朋友关系连双向边。
但是总感觉自己看到题目不能一下想到这是网络流，感觉这些题都是给一个图，求最优之类。
program vote;
type ptype=^node;
node=record
v,w,flow:longint;
op,next:ptype;
end;
const maxn=;
var head:array[..maxn] of ptype;
visit:array[..maxn] of boolean;
q,d:array[..maxn] of longint;
n,m,i,t,x,y,st,ed:longint; function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end; procedure insert(u,v,r,s:longint);
var p1,p2,q:ptype;
begin
new(p1);
p1^.v:=v;p1^.w:=r;p1^.flow:=;p1^.next:=nil;
q:=head[u];
if q=nil then head[u]:=p1 else
begin
while q^.next<>nil do q:=q^.next;
q^.next:=p1;
end;
new(p2);
p2^.v:=u;p2^.w:=s;p2^.flow:=;p2^.next:=nil;
q:=head[v];
if q=nil then head[v]:=p2 else
begin
while q^.next<>nil do q:=q^.next;
q^.next:=p2;
end;
p1^.op:=p2;p2^.op:=p1;
end; function bfs:boolean;
var star,rear,x:longint;
y:ptype;
begin
fillchar(visit,sizeof(visit),false);
fillchar(q,sizeof(q),);fillchar(d,sizeof(d),);
star:=;rear:=;q[star]:=st;visit[st]:=true;d[st]:=;
while star<=rear do
begin
x:=q[star];y:=head[x];
while y<>nil do
begin
if (not visit[y^.v]) and (y^.w>y^.flow) then
begin
inc(rear);
q[rear]:=y^.v;
visit[y^.v]:=true;
d[y^.v]:=d[x]+;
end;
y:=y^.next;
end;
inc(star);
end;
bfs:=visit[ed];
end; function addflow(p,maxflow:longint):longint;
var y:ptype;
o:longint;
begin
if (p=ed) or (maxflow=) then exit(maxflow);
//fillchar(visit,sizeof(visit),false);
visit[p]:=true;
addflow:=;
y:=head[p];
while y<>nil do
begin
if (d[y^.v]=d[p]+) and (y^.w>y^.flow) then
begin
o:=addflow(y^.v,min(maxflow,y^.w-y^.flow));
if o> then
begin
inc(addflow,o);
dec(maxflow,o);
inc(y^.flow,o);
dec(y^.op^.flow,o);
if maxflow= then exit;
end;
end;
y:=y^.next
end;
end; function network:longint;
begin
network:=;
while bfs do
inc(network,addflow(st,maxlongint));
end; begin
//assign(input,'vote.in');reset(input);
//assign(output,'vote.out');rewrite(output);
readln(n,m);
st:=;ed:=n+;
for i:= to n do
begin
read(t);
if t= then insert(st,i,,) else insert(i,ed,,);
end;
for i:= to m do
begin
readln(x,y);
insert(x,y,,);
end;
writeln(network);
//close(input);close(output);
end.
Vote
P.S. 07年该是网络流刚开始风靡那会儿吧，怪不得时限5s，数据也很小…