Nguồn đề bài: http://vn.spoj.com/problems/JOBSET/
1. Đề bài JOBSET spoj
Công ty xây dựng SVI phải lựa chọn các dự án cần thực hiện để lợi nhuận đem lại là nhiều nhất. Công ty có một danh sách gồm n dự án đánh số từ 1 đến n. Sau khi công ty rà soát năng lự thực hiện các dự án, công ty đưa ra bảng đánh giá hiệu quả (có thể là lợi nhuận hoặc thua lỗ) từ việc thực hiện dự án i là pi (nếu pi > 0 đó là lợi nhuận, ngược lại nếu pi < 0 thì đó là thua lỗi phải chị từ việc thực hiện dự án i, |pi| < 10^6). Việc lựa chọn các dự án cần thực hiện để lợi nhuận đem lại là lớn nhất không phải là đơn giản bời vì công ty không thể chi lựa chọn accs công việc đem lại lợi nhuận để thực hiện. Có một danh sách gồm m điều kiện liên quan đến việc lựa chọn thwucj hiện các dự án. Điều kiện thứ j yêu cầu: “Nếu thực hiện dự án uj thì phải thực hiện dự án vj”, j = 1, 2, .., m. Một tập con các dự án được gọi là lựa chọn được nếu mỗi dự án trong nó luông thỏa mãn các điều kiện trong danh sách.
Yêu cầu: Hãy giúp công ty tìm tập các dự án lựa chọn được mà việc thực hiện chúng đem lại tổng hiệu quả lớn nhất.
Input
- Dòng đầu ghi một số nguyên dương n
- Dòng thứ hai ghi n số nguyên tương ứng là tính hiệu quả của từng công việc.
- Dòng thứ bai ghi một số nguyên dương m (m <= 10^4).
- Dòng thứ j trong số m dòng tiếp theo ghi hai số nguyên dương uj và vj chỉ sự ràng buộc rằng nếu thực hiện công việc uj thì phải thực hiện công việc vj.
Output
- Vui lòng ghi ra một số nguyên là tổng hiệu quả của tập các dự có thể án thực hiện tìm được.
- Ghi ra số 0 nếu như không chọn dự án nảo cả.
Giới hạn
- 30% số test có n <= 20.
- 30% số test khác có n <= 100.
- 40% số test còn lại có n <= 500.
Example
Input:
6
10 4 -5 3 -1 -2
4
2 3
2 5
6 5
4 3
Output:
11
2. code tham khảo JOBSET spoj
Pascal
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.
