POJ 1466

 #include<iostream>
#include<stdio.h>
#define MAXN 505
using namespace std; int edge[MAXN][MAXN];
int match[MAXN];
bool ck[MAXN]; int hungary(int num1,int num2);
bool search_dfs(int num1,int num2,int value); int main()
{
//freopen("acm.acm","r",stdin);
int num;
int i;
int j;
int u;
int v;
int s;
int index;
while(scanf("%d",&num) != EOF)
{
for(i = ; i < num; ++ i)
{
edge[i][] = -;
}
for(i = ; i < num; ++ i)
{
scanf("%d",&u);
getchar();
getchar();
getchar();
scanf("%d",&s);
getchar();
getchar();
index = ;
for(j = ; j < s; ++ j)
{
scanf("%d",&v);
edge[u][index ++] = v;
edge[u][index] = -;
}
}
cout<<num - hungary(num,num)/<<endl;
}
} int hungary(int num1,int num2)
{
memset(match,-,sizeof(match));
int i;
int sum = ;
for(i = ; i < num1; ++ i)
{
memset(ck,false,sizeof(ck));
if(search_dfs(num1,num2,i))
++ sum;
}
return sum;
}
bool search_dfs(int num1,int num2,int value)
{
int i;
int t;
i = ;
while(edge[value][i] != -)
{
if(!ck[edge[value][i]])
{
ck[edge[value][i]] = true;
t = match[edge[value][i]];
match[edge[value][i]] = value;
if(t == - || search_dfs(num1,num2,t))
return true;
match[edge[value][i]] = t;
}
++ i;
}
return false;
}

关注我的公众号,当然,如果你对Java, Scala, Python等技术经验,以及编程日记,感兴趣的话。

POJ 1466

技术网站地址: vmfor.com

上一篇:js时间戳转化成日期格式


下一篇:js时间戳转成日期格式