Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# - Tập 3 - Chương 3: Cặp ghép

urn d; 
} 
void Doc(){ 
 memset(c,0,sizeof(c)); 
 ifstream f(fn); 
 f >> n >> m; // n - so hs; m - so ngay 
 int i,j,k,r,q; 
 s[0] = 0; 
 for (i = 1; i <= m; ++i) { 
 f >> r; // so phien trong ngay i 
 s[i] = s[i-1] + r; // s[i] - phien cuoi cua ngay i 
 } 
 sp = s[m]; 
 for (i = 1; i <= n; ++i){ // nguyen vong cua hs i 
 f >> k; // so ngay hs i chon 
 for (r = 1; r <= k; ++r){ 
 f >> j ; // HS i chon ngay j 
 for (q = s[j-1]+1; q <= s[j]; ++q) // duyet theo phien 
 c[i][q] = 1; 
 } 
 } 
 f.close(); 
} 
3.5 Cặp ghép cực đại: Chị Hằng 2 
Nội dung giống bài cặp ghép với một thay đổi như sau: c[i][j] = v cho biết em i yêu thích món quà j với 
mức độ vi, 0  vi  10. Yêu cầu ghép cặp sao cho tổng độ yêu thích đạt max. 
autum2.inp autum2.out Input text file: autum2.inp 
Dòng đầu tiên: hai số n và m, trong đó n là số em nhỏ; m là số 
quà. Tiếp đến là n dòng của ma trận c[1..n,1..m], mỗi dòng m 
số; m  n. 
Output text file: autum2.out 
Dòng đầu tiên: giá trị max tổng độ yêu thích đạt được theo 
phương án ghép cặp đã chọn. Tiếp đến là n dòng, mỗi dòng 2 
số i j cho biết em i nhận quà j. 
5 5 
1 2 3 10 5 
1 2 3 4 11 
12 2 3 4 5 
1 13 3 4 5 
1 2 14 4 5 
60 
1 4 
2 5 
3 1 
4 2 
5 3 
Thuật toán 
Ta quản lí một giá trị dmax là giá trị gia tăng nhiều nhất trong các phương án xếp quà cho em i. Thí dụ, sau 
khi đã xếp quà cho i1 em đầu tiên ta chuyển qua xếp quà cho em i. Giả sử ta có 2 phương án xếp quà cho 
em i. Phương án thứ nhất có thể tăng giá trị dmax lên thêm v1 đơn vị, phương án thứ hai có thể tăng giá trị 
dmax lên thêm v2 > v1 đơn vị. Ta sẽ chọn phương án thứ hai. Để thực hiện điều này ta cần lưu ý mấy giá trị 
sau đây. 
 a[i] là quà em i hiện giữ trên tay, b[j] là em đang giữ quà j. Ta đã biết b[a[i]] = i và a[b[j]] = j, 
ngoài ra, nếu em i chưa được chia quà thì ta đặt a[i] = 0, và nếu món quà j chưa được chia cho em 
nào thì b[j] = 0. 
 c[i,j] là độ yêu thích của em i đối với món quà j mà ta tạm gọi là giá trị của món quà j đối với em i 
hay vắn tắt là giá trị. Để ý rằng cùng một món quà j nhưng em i sẽ đánh giá khác với em k, tức là 
nói chung c[i,j]  c[k,j]. 
Khác với phương pháp ghép cặp không phân biệt mức độ yêu thích trước kia, mỗi khi tìm được một dãy 
liên hoàn em t1 nhận quà từ em t2, t2 nhận quà từ em t3, ..., tk sẽ nhận món quà q chưa chia 
i = t1  t2  … tk1  tk = j (*) 
thì ta đánh giá xem nếu quyết định kết thúc thủ tục Xep(i) bằng cách thực hiện dãy liên hoàn (*) thì giá trị 
gia tăng dmax của phương án này là bao nhiêu và cập nhật giá trị đó. 
Gọi d là giá trị gia tăng của phương án chia quà. Mỗi khi em j nhường quà a[j] của mình cho bạn i để nhận 
quà mới q thì giá trị của phương án sẽ thay đổi như sau: 
 d giảm một lượng c[j,a[j]] khi em j đặt quà a[j] xuống; 
 d tăng một lượng c[j,q] khi em j nhận quà mới q; 
 d tăng một lượng c[i,a[j]] khi em i nhận quà a[j] từ bạn j. 
 Tổng hợp lại, giá trị gia tăng của việc em j nhường quà cho em i để nhận quà mới q sẽ là c[j,q] + c[i,a[j]] – 
c[i,a[j]]. Ta có d := d + c[j,q] + c[i,a[j]] – c[i,a[j]]. 
Kí hiệu d(j) là giá trị gia tăng của phương án khi em j được đưa vào danh sách nhường quà. Phương án này 
bắt đầu bằng việc tìm quà cho em i, do đó d(i) = 0. Mỗi khi đưa j vào danh sách nhường quà cho k ta tính 
được d(j) = d(k) + c[k,a[j]] – c[k,a[j]]. 
Giả sử ta quyết định kết thúc việc tìm quà cho em i, tức là kết thúc thủ tục xét tại dãy (*). Khi đó do em j 
cuối cùng trong dãy nhận quà mới là q thì giá trị gia tăng của phương án sẽ được cộng thêm một lượng 
c[j,q] và bằng d(j) + c[j,q]. Ta so sánh đại lượng này với dmax để ghi nhận tình huống tối ưu. 
(* Autum2.pas *) 
uses crt; 
const fn = 'autum2.inp'; gn = 'autum2.out'; 
mn = 201; { so nguoi va so qua toi da } 
bl = #32; nl = #13#10; 
type mi1 = array[0..mn] of integer; 
 mb2 = array[0..mn,0..mn] of byte; 
var a: mi1; { a[i] = j: em i nhan qua j } 
 b: mi1; { b[j] = i: qua j trong tay em i } 
 t: mi1; { t[j] = i : em j nhuong qua cho ban i } 
 c: mb2; { c[i][j] = 1: i thich qua j } 
 d: mi1; { d[j]: gia tri gia tang tich luy den em j } 
 n: integer; { so em nho } 
 m: integer; { so qua } 
 st: mi1; { stack } 
 p: integer; { tro ngon st } 
 imax, jmax, dmax: integer; 
procedure Ghi(v: integer); 
 var vmax, i: integer; 
 g: text; 
begin 
 vmax := 0; 
 for i := 1 to n do 
 if (a[i] > 0) then vmax := vmax + c[i,a[i]]; 
 assign(g,gn); rewrite(g); 
 writeln(g,vmax); 
 for i := 1 to n do 
 if (a[i] > 0) then writeln(g,i,bl,a[i]); 
 close(g); 
end; 
procedure PrintArray(var a: mi1; d,c: integer); 
{ Hien thi mang a[d..c] } 
 var i: integer; 
begin for i := d to c do write(a[i],bl); end; 
procedure Update(i,j: integer); 
 var c: integer; 
begin 
 repeat 
 c := a[i]; { i bo qua c } 
 a[i] := j; b[j] := i; { i nhan qua moi j } 
 i := t[i]; j := c; { chuyen qua nguoi khac } 
 until c = 0; 
end; 
procedure Mark(i,j: integer); 
{ ghi nhan phuong an i nhan qua j } 
 var sum: integer; 
begin 
 sum := d[i] + c[i,j]; { neu i nhan qua moi j } 
 if (sum > dmax) then { ghi nhan phuong an tot hon } 
 begin 
 dmax := sum; 
 imax := i; jmax := j; 
 end 
end; 
procedure Nap(i,j: integer); 
{ Nap em j vao danh sach nhuong qua cho em i } 
begin 
 if (t[j] > 0) then exit; { j da co trong st } 
 inc(p); st[p] := j; t[j] := i; { j se nhuong qua cho i } 
 { dieu chinh gia tri tich luy } 
 d[j] := d[i] + c[i,a[j]] - c[j,a[j]] ; 
end; 
function Xep(i: integer): integer; { tim qua cho em i } 
 var j: integer; 
begin 
 fillchar(t,sizeof(t),0); d := t; 
 { d[j] - do gia tang tich luy den em j } 
 dmax := 0; p := 0; Nap(i,i); 
 while (p > 0) do 
 begin 
 i := st[p]; dec(p); { lay ngon stack } 
 for j := 1 to m do { duyet cac mon qua } 
 if (b[j] = 0) then Mark(i,j) { qua j chua chia } 
 else Nap(i,j); { danh sach nhuong qua } 
 end; 
 Xep := 0; 
 if (dmax = 0) then exit; 
 Update(imax, jmax); 
 Xep := 1; { Xep duoc qua cho em i } 
end; 
function Par: integer; { Ghep cap } 
 var i, v: integer; 
begin 
 v := 0; 
 fillchar(a,sizeof(a),0); b := a; 
 for i := 1 to n do v := v + Xep(i); 
 Par := v; 
end; 
procedure Print; { Hien thi ma tran c } 
 var i,j: integer; 
begin 
 writeln(nl,' Input: '); 
 for i := 1 to n do 
 begin 
 writeln; 
 for j := 1 to m do write(c[i,j],bl); 
 end; 
end; 
procedure Doc; 
 var f: text; 
 i,j,k,r: integer; 
begin 
 fillchar(c,sizeof(c),0); 
 assign(f,fn); reset(f); 
 readln(f,n,m); 
 for i := 1 to n do 
 for j := 1 to m do 
 read(f,c[i,j]); 
 close(f); 
end; 
procedure Run; 
 var v: integer; 
begin 
 Doc; Print; 
 v := Par; 
 Ghi(v); 
 writeln(nl, ' ket qua: '); PrintArray(a,1,n); 
end; 
BEGIN 
 Run; 
 writeln(nl,' Fini'); 
 readln; 
END. 
// Dev-C++: Autum2 
#include 
#include 
using namespace std; 
// D A T A A N D V A R I A B L E S 
const char * fn = "autum2.inp"; 
const char * gn = "autum2.out"; 
const int mn = 201; // so nguoi va so qua toi da 
int a[mn]; // a[i] = j: em i nhan qua j 
int b[mn]; // b[j] = i: qua j trong tay em i 
int t[mn]; // t[j] = i : em j nhuong qua cho ban i 
int c[mn][mn]; // c[i][j] = 1: i thich qua j 
int d[mn]; // d[j] khi j nhuong qua cho i 
int n; // so em nho 
int m; // so qua 
int st[mn]; // stack 
int p; // con tro stack 
int imax, jmax, dmax; 
// P R O T O T Y P E S 
int main(); 
void Doc(); 
void Print(); 
int Par(); 
int Xep(int); 
void Update(int, int); 
void PrintArray(int [], int , int ); 
void Ghi(int); 
void Nap(int, int); 
void Mark(int, int); 
// I M P L E M E N T A T I O N 
int main() { 
 Doc(); 
 Print(); 
 int v = Par(); 
 Ghi(v); 
 cout << endl << " Ket qua: "; PrintArray(a,1,n); 
 cout << endl; 
 system("PAUSE"); 
 return EXIT_SUCCESS; 
} 
void Ghi(int v) { 
 int vmax = 0; 
 for (int i = 1; i <= n; ++i) 
 if (a[i] > 0) vmax += c[i][a[i]]; 
 ofstream g(gn); 
 g << vmax << endl; 
 for (int i = 1; i <= n; ++i) 
 if (a[i] > 0) g << i << " " << a[i] << endl; 
 g.close(); 
} 
void PrintArray(int a[], int d, int c) { 
 int i; 
 for (i = d; i <= c; ++i) cout << a[i] << " "; 
} 
void Update(int i, int j){ 
 int c; 
 do { 
 c = a[i]; // i bo qua c 
 a[i] = j; b[j] = i; // i nhan qua moi j 
 i = t[i]; j = c; // chuyen qua nguoi khac 
 } while (c > 0); 
} 
void Mark(int i, int j) { 
 int sum = d[i]+c[i][j];// neu i nhan qua moi j 
 if (sum > dmax) { // ghi nhan phuong an tot hon 
 dmax = sum; 
 imax = i; jmax = j; 
 } 
} 
void Nap(int i, int j) { // Nap j vao st 
// em j se nhuong qua a[j] cho em i 
// em i bo qua a[i] de lay a[j] 
 if (t[j]>0) return; // j da co 
 st[++p] = j; t[j] = i; 
 d[j] = d[i] + c[i][a[j]] - c[j][a[j]] ;// do lech 
} 
int Xep(int i) { // tim qua cho em i 
 memset(t, 0, sizeof(t)); 
 memset(d, 0, sizeof(d)); // d[i] - do lech neu i nhuong qua 
 int j; 
 dmax = 0; p = 0; Nap(i,i); 
 while(p > 0) { 
 i = st[p--]; // lay ngon stack 
 for (j = 1; j <= m; ++j) // duyet cac mon qua 
 if (b[j] == 0) Mark(i,j); // qua j chua chia 
 else Nap(i,j);// danh sach nhuong qua 
 } // while 
 if (dmax = 0) return 0; 
 Update(imax, jmax); 
 return 1; // Xep duoc qua cho em i 
} 
int Par(){ // Cap ghep 
 int v = 0, i; 
 memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); 
 for (i = 1; i <= n; ++i) v += Xep(i); 
 return v; 
} 
void Print() { // Hien thi ma tran c 
 cout << endl << " input: "; 
 cout << endl << n << " " << m << endl; 
 int i,j; 
 for (i = 1; i <= n; ++i){ 
 for (j = 1; j <= m; ++j) 
 cout << c[i][j] << " "; 
 cout << endl; 
 } 
} 
void Doc(){ 
 memset(c,0,sizeof(c)); 
 ifstream f(fn); 
 f >> n >> m; 
 int i,j; 
 for (i = 1; i <= n; ++i) 
 for (j = 1; j <= m; ++j) 
 f >> c[i][j]; 
 f.close(); 
}