最大匹配 人员分配 SSL 1338
-
- Description--
- Input--
- Output--
- Sample Input--
- Sample Output--
- 说明--
- 代码--
-
-
- 邻接矩阵
- 邻接表
-
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–
说明–
1<=m,n<=100
1<=s<=10000
代码–
邻接矩阵
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int m, n, s, x, y, ans, l[105], f[105][105];
bool pd[105];
bool find(int o)
{
for (int i = 1; i <= n; ++i)
if (f[o][i] && !pd[i])
{
pd[i] = 1;
int e = l[i];
l[i] = o;
if (!e || find(e)) return 1;
l[i] = e;
}
return 0;
}
int main()
{
scanf("%d%d%d", &m, &n, &s);
for (int i = 1; i <= s; ++i)
{
scanf("%d%d", &x, &y);
f[x][y] = 1;
}
for (int i = 1; i <= m; ++i)
{
memset(pd, 0, sizeof(pd));
if (find(i)) ans++;
}
printf("%d", ans);
return 0;
}
邻接表
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int m, n, s, t, xx, yy, ans, l[105], ls[105];
bool pd[105];
struct yyd
{
int x, next;
}f[10005];
bool find(int o)
{
for (int i = ls[o]; i; i = f[i].next)
{
int k = f[i].x;
if (!pd[k])
{
pd[k] = 1;
int e = l[k];
l[k] = o;
if (!e || find(e)) return 1;
l[k] = e;
}
}
return 0;
}
int main()
{
scanf("%d%d%d", &m, &n, &s);
for (int i = 1; i <= s; ++i)
{
scanf("%d%d", &xx, &yy);
f[++t].x = yy, f[t].next = ls[xx], ls[xx] = t;
}
for (int i = 1; i <= n; ++i)
{
memset(pd, 0, sizeof(pd));
if (find(i)) ans++;
}
printf("%d", ans);
return 0;
}