解构最小顶点覆盖问题

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#define CLR(x) memset(x,0,sizeof(x))
#define __CLR(x) memset(x,-1,sizeof(x))
using namespace std;
 
vector<int>G[1510];
bool vis[1510];
int match[1510];
 
bool dfs(int u)
{
    for(int i=0;i<G[u].size();i++)
    {
        int t=G[u][i];
        if(!vis[t])
        {
            vis[t]=1;
            if(match[t]==-1||dfs(match[t]))
            {
                match[t]=u;
                return true;
            }
        }
    }
    return false;
}
 
int main()
{
    //ios_base::sync_with_stdio(0);
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=0; i<n; i++)
        {
            int m,k;
            scanf("%d:(%d)",&m,&k);
            for(int j=0; j<k; j++)
            {
                int a;
                scanf("%d",&a);
                G[m].push_back(a);
                G[a].push_back(m);
            }
        } 
        int res=0;
        __CLR(match);
        for(int i=0; i<n; i++)
        {
            CLR(vis);
            if(dfs(i))
                res++;
        }
        printf("%d\n",res/2);
        for(int i=0;i<1510;i++)
           G[i].clear();
    }
}

源代码：https://blog.csdn.net/u012294939/article/details/43741775

解释：
1、利用动态开点来储存边，
即u-v的边用a[u][v]表示，（加入的话：a[u].push_back[v];）
2、匈牙利算法的理论应用，最小顶点覆盖数=最大匹配数
3、本题是树状结构的无向无环图（区别于有向无环图），所以会进行补全操作，所以会产生两倍的匹配数目，结果要除2，如果是有向无环图，那么就直接输出就行了
4、本题目的起始位置是0，中止位置是n-1，所以match数组（最大匹配数的匹配对象数组）要初始化为-1
5、关于动态数组a的元素的解释和下标：
第一部分：输入部分：每开一个新的点，就将下标加一，然后将边结点放入。
第二部分：匹配函数部分：范围是由0~sizeof（a[x]）与之相连的每一条边的节点都被遍历，
即 t = G [x] [i] 是一个节点的编号，而不是（下标或者等于布尔型）。
6.没了