解决问题:
N个男的和M个女的,已知道每个男的只能接受哪些女的,求最多能够匹配多少对情侣?
思路:
1.只要求出有多少个男的找到对象即可。
2.遍历所有男的,对于每个男的做以下处理(3~5),最后进入6
3.随便找一个他能够接受的女的,判断这个女的是否被“挑选”过了,没挑选过的则设置为挑选并进入4,否则继续找下一个女的,找遍所有都是挑选过的则进入5
4.判断这个女的是否有男朋友了,没有就直接和上述的男的进行匹配,如果有的话(假设她的男朋友是A),则对A进行3的操作,如果该操作返回的是真,则说明这个女的可以和男的匹配,而A和另外的人匹配。返回真。
5.返回假
6.如果该男的找到女的,则最大匹配数+1.
没说清楚,配合代码吧,很简单的一个模板。
#include <stdio.h>
#include <string.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n,m;
int sum;
int p[201];
int b[201];
int map[201][201];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool path(int cow)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i;
for(i=1;i<=m;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(b[i]==0 && map[cow][i] == 1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
b[i] = 1;
if(p[i]==0 || path(p[i]))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
p[i]=cow;
return true;
}
}
}
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,j;
while(scanf("%d%d",&n,&m)!=EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
sum=0;
memset(map,0,sizeof(map));
memset(p,0,sizeof(p));
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int a,b;
scanf("%d",&a);
for(j=1;j<=a;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d",&b);
map[i][b] = 1;
}
}
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
memset(b,0,sizeof(b));
if(path(i))
sum++;
}
printf("%d\n",sum);
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
下面尝试用邻接表来解决类似的题目,但是如果不释放内存的话,会MLE,而通过free释放内存又会出现TLE错误,太囧了。。。良智说用STL的vector应该可以处理这个问题,回头再用vector,今天先发free的做法,虽然过不了~~
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct edge{
int to;
edge* next;
};
edge list[101];
int p,n;
int par[301];
int b[301];
struct edge* temp;
struct edge* e;
bool path(int person)
{
struct edge* e = list[person].next;
while(e)
{
if(b[e->to]==0)
{
b[e->to] = 1;
if(par[e->to]==0 || path(par[e->to]))
{
par[e->to]=person;
// printf("%d__%d\n",e->to,par[e->to]);
return true;
}
}
e = e->next;
}
return false;
}
int main()
{
int i,j;
int a,t2;
int t;
while(scanf("%d",&t)!=EOF)
{
while(t--)
{
scanf("%d%d",&p,&n);
{
int ans = 0;
//memset(map,0,sizeof(map));
memset(par,0,sizeof(par));
for(i=1;i<=p;i++)
{
scanf("%d",&a);
//list[i] = (struct edge*)malloc(sizeof(edge));
struct edge* head = (&list[i]);
e = head;
while(a--)
{
scanf("%d",&t2);
temp = (struct edge*)malloc(sizeof(edge));
temp->to = t2;
e->next = temp;
e = temp;
}
e->next = NULL;
e = head;
/*
while(e)
{
printf("%d__%d\n",e->from,e->to);
e=e->next;
}*/
}
for(i=1;i<=p;i++)
{
memset(b,0,sizeof(b));
if(path(i))
{
ans++;
}
else
{
printf("NO\n");
break;
}
}
if(ans==p)
printf("YES\n");
for(i=1;i<=p;i++)
{
e = list[i].next;
while(e)
{
temp = e;
e=e->next;
free(temp);
}
}
}
}
}
return 0;
}
posted on 2010-05-16 00:56
ACong 阅读(185)
评论(0) 编辑 收藏 引用