首页 > 代码库 > [SHTSC 2007] 善意的投票

[SHTSC 2007] 善意的投票

我就是来复习Dinic算法的,仅10天不写,我已经退化成写一遍+调试需要接近一个小时了,当然其中不乏在网上乱逛的时间…

赞成从S源点连一条单向边,反对向T汇点连一条单向边,朋友关系连双向边。

但是总感觉自己看到题目不能一下想到这是网络流,感觉这些题都是给一个图,求最优之类。

program vote;type ptype=^node;     node=record          v,w,flow:longint;          op,next:ptype;          end;const maxn=310;var head:array[1..maxn] of ptype;    visit:array[1..maxn] of boolean;    q,d:array[0..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:=0;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:=0;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),0);fillchar(d,sizeof(d),0);  star:=1;rear:=1;q[star]:=st;visit[st]:=true;d[st]:=1;  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]+1;            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=0) then exit(maxflow);  //fillchar(visit,sizeof(visit),false);  visit[p]:=true;  addflow:=0;  y:=head[p];  while y<>nil do    begin      if (d[y^.v]=d[p]+1) and (y^.w>y^.flow) then        begin          o:=addflow(y^.v,min(maxflow,y^.w-y^.flow));          if o>0 then            begin              inc(addflow,o);              dec(maxflow,o);              inc(y^.flow,o);              dec(y^.op^.flow,o);              if maxflow=0 then exit;            end;        end;      y:=y^.next    end;end;function network:longint;begin  network:=0;  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:=0;ed:=n+1;  for i:=1 to n do    begin      read(t);      if t=1 then insert(st,i,1,0) else insert(i,ed,1,0);    end;  for i:=1 to m do    begin      readln(x,y);      insert(x,y,1,1);    end;  writeln(network);  //close(input);close(output);end.
Vote

P.S. 07年该是网络流刚开始风靡那会儿吧,怪不得时限5s,数据也很小…