02/10/2018, 14:41
Hungari Cặp ghép cực đại có trọng số cực tiểu
Nguồn đề bài: http://vn.spoj.com/problems/MATCH2/ 1. Đề bài Cặp ghép cực đại có trọng số cực tiểu Cho đồ thị hai phía G = (X U Y, E); Các đỉnh của X ký hiệu là x1, x2, …, xn, các đỉnh của Y ký hiệu là y1, y2, …, yn. Mỗi cạnh của G được gán một trọng số không âm. Một ...
Nguồn đề bài: http://vn.spoj.com/problems/MATCH2/
1. Đề bài Cặp ghép cực đại có trọng số cực tiểu
Cho đồ thị hai phía G = (X U Y, E); Các đỉnh của X ký hiệu là x1, x2, …, xn, các đỉnh của Y ký hiệu là y1, y2, …, yn. Mỗi cạnh của G được gán một trọng số không âm. Một bộ ghép đầy đủ trên G là một tập n cạnh thuộc E đôi một không có đỉnh chung. Trọng số của bộ ghép là tổng trọng số các cạnh nằm trong bộ ghép.
Ràng buộc: Luôn tồn tại ít nhất một bộ ghép đầy đủ trên G.
Chú ý dùng Eof chứ không dùng SeekEof
Input
• Dòng 1: Chứa số n (1 ≤ n ≤ 200)
• Các dòng tiếp theo, mỗi dòng chứa 3 số nguyên i, j, c cho biết có một cạnh (xi, yj) và trọng số cạnh đó là c (0 ≤ c ≤ 200).
Output
• Dòng 1: Ghi trọng số bộ ghép tìm được
• n dòng tiếp, mỗi dòng ghi hai số (u, v) tượng trưng cho một cạnh (xu, yv) được chọn vào bộ ghép.
Example
Input:
4
1 1 0
1 2 0
2 1 0
2 4 2
3 2 1
3 3 0
4 3 0
4 4 9
Output:
3
1 1
2 4
3 2
4 3
2. Code tham khảo thuật toán Hungari , MATCH2 spoj
Bài này các bạn vui lòng coi thuật toán chi tiết trong sách Lê Minh Hoàng.
const fi=';
nmax=200;
vc=100000000;
type data=longint;
var
f:text;
A:array[0..nmax+1,0..nmax+1] of data;
Fx,Fy,MatchX,MatchY,tr:array[0..nmax+1] of data;
Q:array[0..nmax*nmax] of data;
ddx,ddy:array[0..nmax+1] of boolean;
dau,cuoi,start,finish:data;
n:data;
procedure docfile;
var i,j,u,v,c:data;
begin
assign(f,fi); reset(f);
readln(f,n);
for i:=1 to n do
for j:=1 to n do
a[i,j]:=vc;
while not eof(f) do
begin
readln(f,u,v,c);
a[u,v]:=c;
end;
close(f);
end;
procedure init;
var i,j:data;
begin
fillchar(MatchX,sizeof(matchx),0);
MatchY:=MatchX;
for i:=1 to n do
begin
fx[i]:=vc;
for j:=1 to n do
if fx[i]>a[i,j] then
fx[i]:=a[i,j];
end;
for i:=1 to n do
begin
fy[i]:=vc;
for j:=1 to n do
if a[i,j]-fx[i]<fy[i] then
fy[i]:=a[i,j]-fx[i];
end;
end;
function get(i,j:data):data;
begin
get:=a[i,j]-fx[i]-fy[j];
end;
procedure themvao(x:data);
begin
inc(cuoi);
q[cuoi]:=x;
end;
function layra:data;
begin
layra:=q[dau];
inc(dau);
end;
procedure bfs;
var u,v,j,i:data;
begin
fillchar(tr,sizeof(tr),0);
dau:=1;
cuoi:=0;
themvao(start);
while dau<=cuoi do
begin
u:=layra;
for v:=1 to n do
if (tr[v]=0) and (get(u,v)=0) then
begin
tr[v]:=u;
if matchy[v]=0 then
begin
finish:=v;
exit;
end;
themvao(matchy[v]);
end;
end;
end;
procedure enlager(u:data);
var v,next:data;
begin
repeat
v:=tr[u];
next:=MatchX[v];
MatchX[v]:=u;
MatchY[u]:=v;
u:=next;
until u=0;
end;
procedure subX_addY;
var i,j,delta:data;
begin
fillchar(ddx,sizeof(ddx),false);
ddy:=ddx;
ddx[start]:=true;
for i:=1 to n do
if tr[i]<>0 then
begin
ddx[MatchY[i]]:=true;
ddy[i]:=true;
end;
delta:=vc;
for i:=1 to n do
if ddx[i] then
for j:=1 to n do
if (not ddy[j]) and (delta>get(i,j)) then
delta:=get(i,j);
for i:=1 to n do
begin
if ddx[i] then fx[i]:=fx[i]+delta;
if ddy[i] then fy[i]:=fy[i]-delta;
end;
end;
procedure xuli;
var i,j,res:data;
begin
for i:=1 to n do
begin
start:=i;
finish:=0;
repeat
bfs;
if finish=0 then subx_addy;
until finish<>0;
enlager(finish);
end;
res:=0;
for i:=1 to n do
if MatchX[i]<>0 then
inc(res,a[i,Matchx[i]]);
writeln(res);
for i:=1 to n do
if MatchX[i]<>0 then
writeln(i, ' ',MatchX[i]);
end;
begin
docfile;
init;
xuli;
end.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 | const fi='; nmax=200; vc=100000000; type data=longint; var f:text; A:array[0..nmax+1,0..nmax+1] of data; Fx,Fy,MatchX,MatchY,tr:array[0..nmax+1] of data; Q:array[0..nmax*nmax] of data; ddx,ddy:array[0..nmax+1] of boolean; dau,cuoi,start,finish:data; n:data; procedure docfile; var i,j,u,v,c:data; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do for j:=1 to n do a[i,j]:=vc; while not eof(f) do begin readln(f,u,v,c); a[u,v]:=c; end; close(f); end; procedure init; var i,j:data; begin fillchar(MatchX,sizeof(matchx),0); MatchY:=MatchX; for i:=1 to n do begin fx[i]:=vc; for j:=1 to n do if fx[i]>a[i,j] then fx[i]:=a[i,j]; end; for i:=1 to n do begin fy[i]:=vc; for j:=1 to n do if a[i,j]-fx[i]<fy[i] then fy[i]:=a[i,j]-fx[i]; end; end; function get(i,j:data):data; begin get:=a[i,j]-fx[i]-fy[j]; end; procedure themvao(x:data); begin inc(cuoi); q[cuoi]:=x; end; function layra:data; begin layra:=q[dau]; inc(dau); end; procedure bfs; var u,v,j,i:data; begin fillchar(tr,sizeof(tr),0); dau:=1; cuoi:=0; themvao(start); while dau<=cuoi do begin u:=layra; for v:=1 to n do if (tr[v]=0) and (get(u,v)=0) then begin tr[v]:=u; if matchy[v]=0 then begin finish:=v; exit; end; themvao(matchy[v]); end; end; end; procedure enlager(u:data); var v,next:data; begin repeat v:=tr[u]; next:=MatchX[v]; MatchX[v]:=u; MatchY[u]:=v; u:=next; until u=0; end; procedure subX_addY; var i,j,delta:data; begin fillchar(ddx,sizeof(ddx),false); ddy:=ddx; ddx[start]:=true; for i:=1 to n do if tr[i]<>0 then begin ddx[MatchY[i]]:=true; ddy[i]:=true; end; delta:=vc; for i:=1 to n do if ddx[i] then for j:=1 to n do if (not ddy[j]) and (delta>get(i,j)) then delta:=get(i,j); for i:=1 to n do begin if ddx[i] then fx[i]:=fx[i]+delta; if ddy[i] then fy[i]:=fy[i]-delta; end; end; procedure xuli; var i,j,res:data; begin for i:=1 to n do begin start:=i; finish:=0; repeat bfs; if finish=0 then subx_addy; until finish<>0; enlager(finish); end; res:=0; for i:=1 to n do if MatchX[i]<>0 then inc
Có thể bạn quan tâm
0
|
