Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

爆汉、跑了3.6s,附我的代码,大牛们指点指点啊,不胜感激.Orz

Posted by smwwh at 2010-08-24 16:59:10 on Problem 1466
//有好的代码给我份啊: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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator