题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=237

二分匹配--最小点覆盖模板题

Tips：用邻接矩阵超时，用数组模拟邻接表WA，暂时只有vector<>过了！

代码如下：

//最小点覆盖 = 最大匹配数

//最大独立集 = N - 最大匹配数

#include "stdio.h"  //二分匹配，求最小点覆盖

#include "string.h"

#include "vector"

using namespace std;

#define N 505

int match[N];

bool mark[N];

vector<int> s[N];

bool find(int x,int n)

{

    for(int i=0; i<(int)s[x].size(); i++)

    {

        int y = s[x][i];

        if(!mark[y])

        {

            mark[y] = true;

            if(match[y]==0 || find(match[y],n))

            {

                match[y] = x;

                return true;

            }

        }

    }

    return false;

}

int main()

{

    int T;

    int x,y;

    int i,n,k;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&k);

        for(i=0; i<N; ++i)

            s[i].clear();

        while(k--)

        {

            scanf("%d %d",&x,&y);

            s[x].push_back(y);

        }

        int ans = 0;

        memset(match,0,sizeof(match));

        for(i=1; i<=n; ++i)

        {

            memset(mark,false,sizeof(mark));

            if(find(i,n))

                ans++;

        }

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

    }

    return 0;

}