JOBSET spoj – VOI 2014 – Chọn công việc

const fi='; nmax=500+10; type data=longint; var f:text; ax,ay:array[0..10000] of data; n,m,s,t,dau,cuoi,c:data; p,Q,D,spt:array[0..nmax+1] of data; A,Flow,dsk:array[0..nmax+1,0..nmax+1] of data; free:array[0..nmax+1] of boolean; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); read(f,n); for i:=1 to n do read(f,p[i]); read(f,m); for i:=1 to m do read(f,ax[i],ay[i]); close(f); end; procedure themcanh(u,v:data); begin inc(spt[u]); DSK[u,spt[u]]:=v; end; procedure taodt; var i,j,u,v:data; begin c:=0; for i:=1 to n do if p[i]>0 then inc(c,p[i]); s:=n+1; t:=n+2; fillchar(a,sizeof(a),0); fillchar(spt,sizeof(spt),0); Flow:=a; for i:=1 to n do begin if p[i]>0 then begin A[s,i]:=p[i]; themcanh(s,i); themcanh(i,s); end else begin a[i,t]:=-p[i]; themcanh(i,t); themcanh(t,i); end; end; for i:=1 to m do begin themcanh(ax[i],ay[i]); themcanh(ay[i],ax[i]); a[ax[i],ay[i]]:=c+1; end; n:=n+2; end; procedure themvao(x:data); begin inc(cuoi); q[cuoi]:=x; end; function layra:data; begin layra:=q[dau]; inc(dau); end; function BFS:boolean; var i,j,u,v:data; begin dau:=1; cuoi:=0; for i:=1 to n do d[i]:=0; themvao(s); d[s]:=1; while dau<=cuoi do begin u:=layra; for i:=1 to spt[u] do begin v:=dsk[u,i]; if (d[v]=0) and (A[u,v]>Flow[u,v]) then begin d[v]:=d[u]+1; if v=t then exit(true); themvao(v); end; end; end; exit(false); end; function min(a,b:data):data; begin if a<b then exit(a); exit(b); end; function dfs(x,delta:data):data; var i,j,u,v,y,tl:data; begin if x=t then exit(delta); free[x]:=false; for i:=1 to spt[x] do begin y:=dsk[x,i]; if (free[y]) and (d[y]=d[x]+1) and (a[x,y]>Flow[x,y]) then begin tl:=dfs(y,min(delta,a[x,y]-Flow[x,y])); if tl>0 then begin inc(flow[x,y],tl); dec(flow[y,x],tl); exit(tl); end; end; end; exit(0); end; procedure dinitz; var i,j,tmp,res:data; begin res:=0; while bfs do begin fillchar(free,sizeof(free),true); repeat tmp:=dfs(s,maxlongint); res:=res+tmp; until tmp=0; end; writeln(c-res); end; begin docfile; taodt; dinitz; end.