【算法基础课】题解整合

st数组的作用:i可能喜欢j，而j已经有女朋友，而st[j]==1就是告诉match[j]重新找女朋友时，不要考虑j。

关于重置st数组的一些解释：

首先，st数组的作用是告诉妹子可能存在的男朋友match[j]我想要和你女朋友j交往，让他找个除了j之外的妹子作为女朋友。但是，为何st数组要清空呢？我们可以分情况讨论：

设之前某一次调用find函数为find(last)，当前调用的函数为find(i)。

1. find(last) == false，说明他喜欢的妹子全部和她们现有的男友相守一生，那么，如果不重置st数组，对于目前的单身狗i来说，last喜欢的人他也肯定追不上，而find(last)仅将last喜欢的妹子x打上了标记(st[x]==true)，所以，不重置没有影响；如果重置，i会尝试追求last追求过的妹子z，而z却再也不会找另一个男友（match[z]没有更多的喜欢的人了），所以i也不会追上z，所以对正确性也没有影响。不过，这会使得i再次访问每一个last见过的妹子，导致程序用时更多。
2. find(last) == true，说明他追到了某个妹子y，根据代码，last追到了某个妹子会停止访问下一个喜欢的妹子（如果有的话），也就是说对于单身狗i，他可能可以和y在一起，因为last可能还有更好的选择，但是如果不重置st数组的话，i就失去了和y见面的机会，这显然是错误的。

对于第1点，重不重置无关紧要，但对于情况2，重置st数组才能保证算法正确性，所以要写memset(st, 0, sizeof st)。

3 3 4
1 6
1 4
2 5
3 4

这组数据也许能够帮助到您，需要注意的是，根据存图方式的不同，您可能需要更换

1 6
1 4

的顺序，使得先遍历到1 4这条边。

例如，如果使用vector存边，由于先加入先访问，需改为

3 3 4
1 4
1 6
2 5
3 4

模板在下面：

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 510, M = 100010;

int h[N], e[M], ne[M], idx;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool st[N];
int match[N];

bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (!match[j] || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

int main()
{
    memset(h, -1, sizeof h);

    int n1, n2, m;
    scanf("%d%d%d", &n1, &n2, &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    int ans = 0;

    // 给左半边的点匹配
    for (int i = 1; i <= n1; i ++ )
    {
        memset(st, 0, sizeof st);
        int t = find(i);
        if (t) ans ++ ;
    }

    printf("%d\n", ans);

    return 0;
}