题目描述

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

思路

邻接表模板

#include <stdio.h>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
#define maxn 101
#define fill(x, y) memset(x, y, sizeof(x))
int n, m, s, v;
double sqr(double a){return a * a;}
int link[maxn];
struct edge
{
    int to, next;
}e[10001];
int ls[10001];
bool fl[maxn];
int find(int x)
{
    for (int i = ls[x]; i; i = e[i].next)
        if (! fl[e[i].to])
        {
            int q = link[e[i].to]; link[e[i].to] = x; fl[e[i].to] = 1;
            if (q == 0 || find(q)) return true;
            link[e[i].to] = q;
        } 
    return false;
}
int tot()
{
    int ans = 0;
    fill(link, 0);
    for (int i = 1; i <= n; i++)
    {
        fill(fl, false);
        if (find(i)) ans++;
    }
    return ans;
}
int main()
{
    scanf("%d%d", &n, &m);
    int t, l = 0;
    scanf("%d", &t);
    for (int i = 1; i <= t; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        e[++l] = (edge) {y, ls[x]};
        ls[x] = l;
    }

    printf("%d\n", tot());
}