本文主要是介绍最大匹配 人员分配 二分图样板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最大匹配 人员分配
Time Limit:1000MS Memory Limit:65536K
Total Submit:112 Accepted:57
Description
设有M个工人x1, x2, …, xm，和N项工作y1, y2, …, yn，规定每个工人至多做一项工作，而每项工作至多分配一名工人去做。由于种种原因，每个工人只能胜任其中的一项或几项工作。问应怎样分配才能使尽可能多的工人分配到他胜任的工作。这个问题称为人员分配问题。
Input
第一行两个整数m，n分别为工人数和工作数。
接下来一个整数s，为二分图的边数。
接下来s行，每行两个数ai,bi表示第ai个工人能胜任第bi份工作
Output
一个整数，表示最多能让多少个工人派到自己的胜任的工作上。
Sample Input
3 3
4
1 2
2 1
3 3
1 3
Sample Output
3 Hint
规模：
1<=m,n<=100
1<=s<=10000
Source
cwj
-
varmap:array[0..101,0..101] of boolean;link:array[0..101] of longint;cover:array[0..101] of boolean;i,j,n,m,s,ans,x,y:longint;function find(i:longint):boolean;vark,q:longint; beginfind:=true;for k:=1 to n doif map[i,k] and not(cover[k])then beginq:=link[k];link[k]:=i;cover[k]:=true;if (q=0) or find(q) then exit;link[k]:=q;end;find:=false; end;procedure main;vari:longint; beginfor i:=1 to n dobeginfillchar(cover,sizeof(cover),0);find(i);end; end;beginreadln(m,n);readln(s);for i:=1 to s dobeginreadln(x,y);map[x,y]:=true;end;main;for i:=1 to n doif link[i]<>0 then inc(ans);writeln(ans); end.
这篇关于最大匹配 人员分配 二分图样板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
