I - Strategic Game - hdu 1054(最小点覆盖)

时间:2024-07-21 19:36:26
题意:用最小的点来覆盖全部的边,因为二分图里面最大的匹配就是最小覆盖,所以直接匹配一下即可
***********************************************************************
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std; const int MAXN = 1505;
const int oo = 1e9+7; struct Edge{int v, next;}e[MAXN*4];///数组开小RE了一次
int Head[MAXN], cnt; int Mx[MAXN], My[MAXN];
int dx[MAXN], dy[MAXN];
int used[MAXN], N, depth; void InIt()
{
    cnt = 0;
    memset(Head, -1, sizeof(Head));
    memset(Mx, -1, sizeof(Mx));
    memset(My, -1, sizeof(My));
}
void AddEdge(int u, int v)
{
    e[cnt].v = v;
    e[cnt].next = Head[u];
    Head[u] = cnt++;
}
bool BFS()
{
    queue<int> Q;
    depth = oo;     memset(dx, false, sizeof(dx));
    memset(dy, false, sizeof(dy));     for(int i=0; i<N; i++)
    {
        if( Mx[i] == -1 )
        {
            dx[i] = true;
            Q.push(i);
        }
    }     while(Q.size())
    {
        int u = Q.front();Q.pop();         if(dx[u] > depth)break;         for(int j=Head[u]; j!=-1; j=e[j].next)
        {
            int v = e[j].v;
            if( dy[v] == false )
            {
                dy[v] = dx[u] + 1;
                if(My[v] == -1)
                    depth = dy[v];
                else
                {
                    dx[ My[v] ] = dy[v] + 1;
                    Q.push( My[v] );
                }
            }
        }
    }     return depth != oo;
}
bool DFS(int i)
{
    for(int j=Head[i]; j!=-1; j=e[j].next)
    {
        int v = e[j].v;
        if( used[v] == false && dx[i] == dy[v]-1 )
        {
            used[v] = true;
            if(My[v] != -1 && dy[v] == depth)
                continue;
            if(My[v] == -1 || DFS(My[v]))
            {
                My[v] = i;
                Mx[i] = v;                 return true;
            }
        }
    }     return false;
}
int Karp()
{
    int ans = 0;     while( BFS() == true)
    {
        memset(used, false, sizeof(used));
        for(int i=0; i<N; i++)
        {
            if( Mx[i] == -1 && DFS(i) )
                ans ++;
        }
    }     return ans;
} int main()
{
    while(scanf("%d", &N) != EOF)
    {
        int M, i, u, v;         InIt();         for(i=0; i<N; i++)
        {
            scanf("%d:(%d)", &u, &M);
            while(M--)
            {
                scanf("%d", &v);
                AddEdge(u, v);
                AddEdge(v, u);
            }
        }         int ans = Karp();         printf("%d\n", ans/2);
    }     return 0;
}