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

100题留纪念 map记得清零

Posted by soledada at 2013-08-23 14:52:34 on Problem 2239
还算比较容易啦
map忘记清零WA

#include <iostream>
using namespace std;
#define SIZE 2000
#define COUR 300
bool chk[SIZE];//相当于check
int match[SIZE];
int map[SIZE][SIZE];
int n,m;//左边的点的个数 右边的点的个数

int dfs(int p)//P点进行查找,找到则增广
{
	int i,t;
	for(i=1+COUR;i<=127+COUR;i++)//需要配置!!
		if(map[p][i] && !chk[i])//找p的一个对应点且该店没有检查过(尝试更新i的匹配)
		{
			chk[i]=1;
			t=match[i];
			match[i]=p;
			if(t==-1 || dfs(t))//如果t是一个初始值,表示i点原来没有匹配,则增广成功返回或者特点能重新找到一个新的匹配点
				return 1;
			match[i]=t;//不成立则改回来哦亲
		}
	return 0;
}
void Pro()
{
	int i,res=0;
	memset(match,-1,sizeof(match));
	for(i=1;i<=n;i++)	//需要配置!!
	{
		memset(chk,0,sizeof(chk));
		res+=dfs(i);
	}
	cout<<res<<endl;
}

/*
模板参数配置: n:左边点的个数 m右边点的个数 l:13、27的结束范围
*/
int main()
{
	freopen("in.txt","r",stdin);
	int i,j,k,a,b;
	while(scanf("%d",&n)!=EOF)
	{
		memset(map,0,sizeof(map));
		for(i=1;i<=n;i++)
		{
			scanf("%d",&j);
			while(j--)
			{
				scanf("%d%d",&a,&b);
				b*=10;
				b+=a;
				b+=COUR;
				map[i][b]=1;
				map[b][i]=1;
			}
		}
		Pro();
	}
	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