匹配（工作分配问题）

设有M个工人x₁,x₂, …, x_m&＃xff0c;和N项工作y₁,y₂, …, y_n&＃xff0c;规定每个工人至多做一项工作&＃xff0c;而每项工作至多分配一名工人去做。由于种种原因&＃xff0c;每个工人只能胜任其中的一项或几项工作。问应怎样分配才能使尽可能多的工人分配到他胜任的工作。这个问题称为人员分配问题。

人员分配问题可以用图的语言来表述。令X&＃61;{x₁, x₂, …, x_m}&＃xff0c;Y&＃61;{y₁, y₂, …,y_n}&＃xff0c;构造二分图G&＃61;(X, Y, E)如下&＃xff1a;

对于1≤i≤m&＃xff0c;1≤j≤n&＃xff0c;当且仅当工人x_i胜任工作y_i时&＃xff0c;G中有一条边x_iy_i&＃xff0c;于是人员分配问题就成为在G中求一个最大匹配的问题。

标程&＃xff1a;

type

 node&＃61;record

 x,y,next:longint;

end;

const

 maxn&＃61;100;

 maxv&＃61;3000;

var

 g:array [1..maxv] of node;

 ls,link:array [1..maxn] of longint;

 cover:array [1..maxn] of boolean;

 n,e,m:longint;

procedure init;

 vari,x,y:longint;

begin

 readln(m,n);

 readln(e);

 fori:&＃61;1 to e do

 begin

  with g[i] do

   begin

    readln(x,y);

    next:&＃61;ls[x];

    ls[x]:&＃61;i;

   end;

 end;

end;

function find(p:longint):boolean;

var

 t,q:longint;

begin

 find:&＃61;true;

 t:&＃61;ls[p];

 while t>0 do

   with g[t] do

     begin

       if cover[y]&＃61;false then

         begin

           cover[y]:&＃61;true;

           q:&＃61;link[y];

           link[y]:&＃61;p;

           if (q&＃61;0) or find(q) then exit;

           link[y]:&＃61;q;

         end;

       t:&＃61;next;

     end;

 find:&＃61;false;

end;

procedure main;

 vari:longint;

begin

 fori:&＃61;1 to n do

 begin

  fillchar(cover,sizeof(cover),0);

  find(i);

 end;

end;

procedure print;

 var

 i,s:longint;

begin

 s:&＃61;0;

 fori:&＃61;1 to n do

  iflink[i]<>0 then s:&＃61;s&＃43;1;

 writeln(s);

{ for i:&＃61;1 to n do

  iflink[i]<>0 then writeln(link[i],&＃39; &＃39;,i);}

end;

begin

 init;

 main;

 print;

end.