poj1466

这题考察的是最大独立集问题，  算是裸的二分匹配， 只要在计算上添加一个n - count/2 就可以直接得出结果了。

不管是男的还是女的都一样，因为你男的算一边，女的再算一遍，这样算两遍， 不管你这个学号是男的还是女的，一点影响都没有。

#include"stdio.h"
#include"string.h"
#define maxn 505

int e[maxn][maxn], n, m, dist[maxn], visit[maxn];

void Init()
{
int i, j, u, v, num;
char chr;

    memset(e, 0, sizeof(e));
    memset(dist, 0, sizeof(dist));

for (i=1; i<= n; i++)
    {
        scanf("%d", &u);
        u++;
while (scanf("%c", &chr), chr!= ':');
while (scanf("%c", &chr), chr!= '(');
        scanf("%d", &num);
while (scanf("%c", &chr), chr!= ')');


for (j=1; j<=num; j++)
        {
            scanf("%d", &v);
            v++;
            e[u][0]++; e[u][e[u][0]] = v;
        }
    }
return;
}

int Dfs(int now)
{
int i, v;

for (i=1; i<=e[now][0]; i++)
    {
        v = e[now][i];
if (visit[v] == 1 )continue;
        visit[v] = 1;
if (dist[v] == 0 || Dfs(dist[v]) == 1)
        {
            dist[v] = now;
return 1;
        }
    }
return 0;
}

void Funs()
{
int i, count = 0;

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

        memset(visit, 0, sizeof(visit));
if (Dfs(i) == 1)count ++;

    }
    printf("%d\n", n - count/2);
return ;
}

int main()
{
while (scanf("%d", &n)!= EOF)
    {
        Init();
        Funs();
    }
return 0;
}