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