| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
爆汉、跑了3.6s,附我的代码,大牛们指点指点啊,不胜感激.Orz//有好的代码给我份啊:smwwh@qq.com
//二分图的最大匹配数
//模板开始
#include<iostream>
using namespace std;
#define MAXN 501
#define MAXM 501
//map[i][j]用来表示i,j是否可达
bool map[MAXN][MAXM];
bool used[MAXM];
int match[MAXM];
//N: 匹配方个数 (都是从1开始,1-N)
//M: 被匹配方个数
int N, M;
bool dfs(int k)
{
for(int i=1; i<=M; i++)
{
if(!used[i] && map[k][i])
{
used[i] = 1;
if(match[i] == -1 || dfs(match[i]))
{
match[i] = k;
return 1;
}
}
}
return 0;
}
int hungary()
{
int max = 0;
memset(match, -1, sizeof(match));
for(int i=1; i<=N; i++)
{
memset(used, 0, sizeof(used));
if(dfs(i))
max++;
}
return max; //返回最大匹配数
}
//模板结束
int main()
{
//freopen("in.txt", "r", stdin);
int stu, girl, boy, num, max;
while(scanf("%d", &stu) != EOF)
{
N = M = stu;
memset(map, 0, sizeof(map));
for(int i=0; i<stu; i++)
{
scanf("%d%*c", &girl);
scanf(" (%d)", &num);
if(num != 0)
{
while(num--)
{
scanf("%d", &boy);
map[girl+1][boy+1] = 1;
}
}
}
//最大独立集数D = 顶点数V - 最小点覆盖数C
//最小点覆盖数C = 最大匹配数M
max = hungary();
printf("%d\n", N - (max+1)/2);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator