当前位置: 代码迷 >> 综合 >> 人员分配 ssl1338
  详细解决方案

人员分配 ssl1338

热度:34   发布时间:2023-10-09 12:55:11.0

题目大意

  设有M个工人x1,x2, …, xm,和N项工作y1, y2, …, yn,规定每个工人至多做一项工作,而每项工作至多分配一名工人去做。由于种种原因,每个工人只能胜任其中的一项或几项工作。问应怎样分配才能使尽可能多的工人分配到他胜任的工作。


题解

求最大匹配常用匈牙利算法,就是从当前匹配(初始为0)出发,检查每一个未标记点,然后从它出发寻找增广路,找到可增广路,就沿着这条增广路进行补充,知道不存在增广路为止。


代码

function find(p:longint):longint;

var

  t,q:longint;

begin

  find:=true;

  t:=ls[p];

  while t>0 do

    with g[t] do

      begin

        if v[y]=0 then

          begin

            v[y]:=1;

            q:=link[y];

            link[y]:=p;

            if (q=0) or find(q) then exit;

            link[y]:=q;

          end;

        t:=next;

     end;

  find:=false;

end;

procedure match;

var

  i,ans:longint;

begin

 fillchar(link,sizeof(link),0);

 for i:=1 to n do

   begin

     fillchar(v,sizeof(v),0);

     if find(i)then ans:=ans+1;

   end;

 writeln(ans);

end;


  相关解决方案