|
|
Posted on 2009-08-28 10:35 reiks 阅读(597) 评论(0) 编辑 收藏 引用 所属分类: 算法与数据结构
 #include<iostream>
bool map[102][302],use[302];
int link[302],n,m;
bool dfs(int);
int main()
   {
 int t,v,i,j,x,num;
scanf("%d",&t);
while (t--)
  {
scanf("%d%d",&n,&m);
i=1;
while (i<=n)
{
j=1;
while (j<=m)
map[i][j++]=0;
i++;
 }
// m ->人 n ->课程
i=1;
while (i<=m)
link[i++] = -1;
i=1;
while (i<=n)
{
scanf("%d",&v);
j=0;
while (j<v)
{
scanf("%d",&x);
map[i][x]=1;
j++;
}
i++;
}
num=0;
i=1;
while (i<=n)
{
j=1;
while (j<=m)
use[j++]=0;
if (dfs(i))
num++;
i++;
}
if (num==n)
printf("YES\n");
else
printf("NO\n");
}
return 0;
 }
bool dfs(int x)
{
int i,j;
i=1;
while (i<=m)
{
if (use[i]==0&&map[x][i])
{
use[i]=1;
j=link[i];
link[i]=x;
if (j==-1||dfs(j))
{
return true;
}
link[i]=j;
}
i++;
}
return false;
}
============================================
#include <memory.h>
#include <stdio.h>
//分别定义左右最大元素
#define LEFT_MAX 501
#define RIGHT_MAX 501
bool useif[RIGHT_MAX];
//link[]记录与右边元素连接的元素，-1表示没有连接
int link[RIGHT_MAX];
int left_num,right_num;
bool array[LEFT_MAX][RIGHT_MAX];
bool can(int t)
{
int i;
for(i=0;i<right_num;i++)
{
if(!useif[i]&&array[t][i])
{
useif[i]=true;
if(link[i]==-1||can(link[i]))
{
link[i]=t;
return true;
}
}
}
return false;
}
int main()
{
int i,k,num,temp,num_of_this;
char c;
//scanf("%d\n",&count);
//for(j=0;j<count;j++)
while(scanf("%d",&left_num)!=-1)
{
right_num=left_num;
//link??-1
memset(link,0xFF,sizeof(link));
memset(array,0,sizeof(array));
memset(useif,0,sizeof(useif));
num=0;
for(i=0;i<left_num;i++)
{
scanf("%d%c%c%c%d%c",&temp,&c,&c,&c,&num_of_this,&c);
for(k=0;k<num_of_this;k++)
{
scanf("%d",&temp);
array[i][temp]=true;
}
}
//匹配，num为结果
for(i=0;i<left_num;i++)
{
memset(useif,0,sizeof(useif));
if(can(i))
num++;
}
printf("%d\n",left_num-num/2);
}
return 1;
}
|