?? pku1466.cpp
字號(hào):
#include <stdio.h>
#define SIZE 510
typedef struct
{
int id;
int next;
} Node;
int N;
Node nd[250000];
int chk[SIZE];
int match[SIZE];
int End;
int DFS(int p)
{
int i, t;
int hd = nd[p].next;
while (hd != -1)
{
i = nd[hd].id;
if (!chk[i])
{
chk[i] = 1;
t = match[i];
match[i] = p;
if (t == -1 || DFS(t))
{
return 1;
}
match[i] = t;
}
hd = nd[hd].next;
}
return 0;
}
void Insert(int hd, int id)
{
nd[End].id = id;
nd[End].next = -1;
while (nd[hd].next != -1)
{
hd = nd[hd].next;
}
nd[hd].next = End;
End++;
}
int main()
{
int i, j, n, one, other;
int ans;
while (scanf("%d", &N) != -1 && N > 0)
{
memset(nd, -1, sizeof(nd));
End = 600;
for (i = 0; i < N; i++)
{
scanf("%d: (%d)", &one, &n);
for (j = 0; j < n; j++)
{
scanf("%d", &other);
Insert(i, other);
}
}
ans = 0;
memset(match, -1, sizeof(match));
for (i = 0; i < N; i++)
{
memset(chk, 0, sizeof(chk));
ans += DFS(i);
}
printf("%d\n", N - ans / 2);
}
return 0;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -