首页 > 代码库 > [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.
P.S. 07年该是网络流刚开始风靡那会儿吧,怪不得时限5s,数据也很小…
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。