解决问题：
N个男的和M个女的，已知道每个男的只能接受哪些女的，求最多能够匹配多少对情侣？
思路：
1.只要求出有多少个男的找到对象即可。
2.遍历所有男的，对于每个男的做以下处理（3~5），最后进入6
3.随便找一个他能够接受的女的，判断这个女的是否被“挑选”过了，没挑选过的则设置为挑选并进入4，否则继续找下一个女的，找遍所有都是挑选过的则进入5
4.判断这个女的是否有男朋友了，没有就直接和上述的男的进行匹配，如果有的话（假设她的男朋友是A)，则对A进行3的操作，如果该操作返回的是真，则说明这个女的可以和男的匹配，而A和另外的人匹配。返回真。
5.返回假
6.如果该男的找到女的，则最大匹配数+1.
没说清楚，配合代码吧，很简单的一个模板。
#include <stdio.h>
#include <string.h>
int n,m;
int sum;
int p[201];
int b[201];
int map[201][201];
bool path(int cow)
{
int i;
for(i=1;i<=m;i++)
{
if(b[i]==0 && map[cow][i] == 1)
{
b[i] = 1;
if(p[i]==0 || path(p[i]))
{
p[i]=cow;
return true;
}
}
}
return false;
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
sum=0;
memset(map,0,sizeof(map));
memset(p,0,sizeof(p));
for(i=1;i<=n;i++)
{
int a,b;
scanf("%d",&a);
for(j=1;j<=a;j++)
{
scanf("%d",&b);
map[i][b] = 1;
}
}
for(i=1;i<=n;i++)
{
memset(b,0,sizeof(b));
if(path(i))
sum++;
}
printf("%d\n",sum);
}
return 0;
}
下面尝试用邻接表来解决类似的题目，但是如果不释放内存的话，会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 阅读(187)
评论(0) 编辑 收藏 引用