解決問題：
N個男的和M個女的，已知道每個男的只能接受哪些女的，求最多能夠匹配多少對情侶？
思路：
1.只要求出有多少個男的找到對象即可。
2.遍歷所有男的，對于每個男的做以下處理（3~5），最后進(jìn)入6
3.隨便找一個他能夠接受的女的，判斷這個女的是否被“挑選”過了，沒挑選過的則設(shè)置為挑選并進(jìn)入4，否則繼續(xù)找下一個女的，找遍所有都是挑選過的則進(jìn)入5
4.判斷這個女的是否有男朋友了，沒有就直接和上述的男的進(jìn)行匹配，如果有的話（假設(shè)她的男朋友是A)，則對A進(jìn)行3的操作，如果該操作返回的是真，則說明這個女的可以和男的匹配，而A和另外的人匹配。返回真。
5.返回假
6.如果該男的找到女的，則最大匹配數(shù)+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;
}
下面嘗試用鄰接表來解決類似的題目，但是如果不釋放內(nèi)存的話，會MLE，而通過free釋放內(nèi)存又會出現(xiàn)TLE錯誤，太囧了。。。良智說用STL的vector應(yīng)該可以處理這個問題，回頭再用vector，今天先發(fā)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 閱讀(194)
評論(0) 編輯 收藏 引用