02/10/2018, 14:18
ASSIGN1 spoj – Phân công hoàn thành sớm nhất
Nguồn đề bài: http://vn.spoj.com/problems/ASSIGN1/ 1. Đề bài ASSIGN1 spoj Có n người, n việc (1 < n ≤ 200). Người thứ i thực hiện công viêc j mất C[i,j] đơn vị thời gian. Giả sử tất cả bắt đầu vào thời điểm 0, hãy tìm cách bố trí mỗi công việc cho mỗi người sao cho thời ...
Nguồn đề bài: http://vn.spoj.com/problems/ASSIGN1/
1. Đề bài ASSIGN1 spoj
Có n người, n việc (1 < n ≤ 200). Người thứ i thực hiện công viêc j mất C[i,j] đơn vị thời gian. Giả sử tất cả bắt đầu vào thời điểm 0, hãy tìm cách bố trí mỗi công việc cho mỗi người sao cho thời điểm hoàn thành công việc là sớm nhất có thể.
Input
– Dòng đầu: N
– Tiếp theo là ma trận C[i,j]. (thuộc kiểu Integer)
Output
– Ghi thời điểm sớm nhất hoàn thành.
Example
Input:
4
10 10 10 2
10 10 3 10
4 10 10 10
10 5 10 10
Output:
5
2. Thuật toán ASSIGN1 SPOJ
– sử dụng chặt nhị phân thời gian nhỏ nhất thỏa mãn, giả sử đang chặt tới thời điểm mid, xây dựng một đồ thị gồm các cạnh có trọng số <=mid, sau đó tôi tìm xem có the ghép N công việc cho N người hay không (sử dụng kiến thức cặp ghép). Nếu thỏa mãn thì chặt nhỏ thời gian thỏa mãn, ngược lại chặt tăng thời gian thỏa mãn.
– Code cặp ghép các bạn có thể tìm trên site
3. code tham khảo C++ và pascal ASSIGN1 spoj
a. Code pascal
const fi=';
nmax=201;
type data=integer;
var
f:text;
A:array[0..nmax+1,0..nmax+1] of data;
n:data;
Q:array[0..nmax*nmax] of data;
tr,MatchX,MatchY:array[0..nmax] of data;
dau,cuoi,mid:data;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
readln(f,n);
for i:=1 to n do
for j:=1 to n do
read(f,a[i,j]);
close(f);
end;
procedure them(x:data);
begin
inc(cuoi);
q[cuoi]:=x;
end;
function lay:data;
begin
lay:=q[dau];
inc(dau);
end;
function BFS:data;
var i,j,u,v:data;
begin
for i:=1 to n do
tr[i]:=0;
dau:=1;
cuoi:=0;
for i:=1 to n do
if MatchX[i]=0 then
them(i);
while dau<=cuoi do
begin
u:=lay;
for v:=1 to n do
if (a[u,v]<=mid) and (tr[v]=0) then
begin
tr[v]:=u;
if MatchY[v]=0 then
exit(v);
them(MatchY[v]);
end;
end;
EXIT(0);
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;
function slove:boolean;
var i,j,d:data;
begin
for i:=1 to n do
begin
Matchx[i]:=0;
Matchy[i]:=0;
end;
repeat
d:=bfs;
if d<>0 then
Enlager(d);
until d=0;
for i:=1 to n do
if Matchx[i]=0 then
exit(false);
exit(true);
end;
procedure xuli;
var i,j:data;
begin
i:=0;
j:=maxint;
while i<j do
begin
mid:=(i+j) shr 1;
if Slove then
j:=mid
else
i:=mid+1;
end;
writeln(i);
end;
begin
docfile;
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 | const fi='; nmax=201; type data=integer; var f:text; A:array[0..nmax+1,0..nmax+1] of data; n:data; Q:array[0..nmax*nmax] of data; tr,MatchX,MatchY:array[0..nmax] of data; dau,cuoi,mid:data; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do for j:=1 to n do read(f,a[i,j]); close(f); end; procedure them(x:data); begin inc(cuoi); q[cuoi]:=x; end; function lay:data; begin lay:=q[dau]; inc(dau); end; function BFS:data; var i,j,u,v:data; begin for i:=1 to n do tr[i]:=0; dau:=1; cuoi:=0; for i:=1 to n do if MatchX[i]=0 then them(i); while dau<=cuoi do begin u:=lay; for v:=1 to n do if (a[u,v]<=mid) and (tr[v]=0) then begin tr[v]:=u; if MatchY[v]=0 then exit(v); them(MatchY[v]); end; end; EXIT(0); 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; function slove:boolean; var i,j,d:data; begin for i:=1 to n do begin Matchx[i]:=0; Matchy[i]:=0; end; repeat d:=bfs; if d<>0 then Enlager(d); until d=0; for i:=1 to n do if Matchx[i]=0 then exit(false); exit(true); end; procedure xuli; var i,j:data; begin i:=0; j:=maxint; while i<j do begin mid:=(i+j) shr 1; if Slove then j:=mid else i:=mid+1; end; writeln(i); end; begin docfile; xuli; end. |
b. Code c++
#include<cstdio>
#include<cstring>
#include<climits>
#include<vector>
#include<queue>
using namespace std;
int c[201][201];
int matchX[201]={0},matchY[201]={0},d[201],n,tim;
int find_match(int x)
{
queue<int> q;
q.push(x);
memset(d,0,sizeof d);
while(!q.empty())
{
int u=q.front();q.pop();
for(int v=1;v<=n;++v) if(c[u][v]<=tim && !d[v])
{
d[v]=u;
if(!matchY[v]) return v;
q.push(matchY[v]);
}
}
return 0;
}
void enlarge(int y)
{
int x,next;
while(y)
{
x=d[y];
next=matchX[x];
matchX[x]=y;
matchY[y]=x;
y=next;
}
}
bool check(int mid)
{
int i,j;
tim=mid;
memset(matchX,0,sizeof matchX);
memset(matchY,0,sizeof matchY);
for(i=1;i<=n;++i) if(!matchX[i])
{
j=find_match(i);
if(j) enlarge(j);
}
for(i=1;i<=n;++i) if(!matchX[i]) return 0;
return 1;
}
int main()
{
//freopen("test.inp","r",stdin);
int i,j;
scanf("%d",&n);
for(i=1;i<=n;++i) for(j=1;j<=n;++j) scanf("%d",&c[i][j]);
i=0;j=INT_MAX;
while(i<j)
{
int mid=(i+j)>>1;
if(check(mid)) j=mid;
else i=mid+1;
}
printf("%d",i);
}
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 | #include<cstdio> #include<cstring> #include<climits> #include<vector> #include<queue> using namespace std; int c[201][201]; int matchX[201]={0},matchY[201]={0},d[201],n,tim; int find_match(int x) { queue<int> q; q.push(x); memset(d,0,sizeof d); while(!q.empty()) { int u=q.front();q.pop(); for(int v=1;v<=n;++v) if(c[u][v]<=tim && !d[v]) { d[v]=u; if(!matchY[v]) return v; q.push(matchY[v]); } } return 0; } void enlarge(int y) { int x,next; while(y) { x=d[y]; next=matchX[x]; matchX[x]=y; matchY[y]=x; y=next; } } bool check(int mid) { int i,j; tim=mid; memset(matchX,0,sizeof matchX); memset(matchY,0,sizeof matchY); for(i=1;i<=n;++i) if(!matchX[i]) { j=find_match(i); if(j) enlarge(j); } for(i=1;i<=n;++i) if(!matchX[i]) return 0; return 1; } int main() { //freopen("test.inp","r",stdin); int i,j; scanf("%d",&n); for(i=1;i<=n;++i) <
Có thể bạn quan tâm
0
|
