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

Re:第一题匈牙利二分图

Posted by guyindu at 2016-01-06 13:35:58 on Problem 3020
In Reply To:Re:第一题匈牙利二分图 Posted by:guyindu at 2016-01-06 13:35:31
wa,哪里错了?
> #include<cstdio>
> #include<cstdlib>
> #include<cstring>
> using namespace std;
> 
> bool xihuan[405][405];
> int dui[405][405],dui1[405][405];
> 
> bool zhao(int x,int y,int lx,int ly)
> {
> 	if(xihuan[x][y-1] && y>1 && y-1!=ly)
> 	{
> 		if(dui[x][y-1]==0)
> 		{
> 			dui[x][y]=x;
> 			dui1[x][y]=y-1;
> 			dui[x][y-1]=x;
> 			dui1[x][y-1]=y;
> 			return true;
> 		}
> 		if(zhao(dui[x][y-1],dui1[x][y-1],x,y-1)&&(dui[x][y-1]!=lx || dui1[x][y-1]!=ly))
> 		{
> 			dui[x][y]=x;
> 			dui1[x][y]=y-1;
> 			dui[x][y-1]=x;
> 			dui1[x][y-1]=y;
> 			return true;
> 		}
> 	}
> 	if(xihuan[x-1][y] && x>1 && x-1!=lx)
> 	{
> 		if(dui[x-1][y]==0)
> 		{
> 			dui[x][y]=x-1;
> 			dui1[x][y]=y;
> 			dui[x-1][y]=x;
> 			dui[x-1][y]=y;
> 			return true;
> 		}
> 		if(zhao(dui[x-1][y],dui1[x-1][y],x-1,y)&&(dui[x-1][y]!=lx || dui1[x-1][y]!=ly))
> 		{
> 			dui[x][y]=x-1;
> 			dui1[x][y]=y;
> 			dui[x-1][y]=x;
> 			dui1[x-1][y]=y;
> 			return true;
> 		}
> 	}
> 	return false;
> }
> 
> int main()
> {
> 	int T,n,m;char c;
> 	scanf("%d",&T);
> 	for(int p=1;p<=T;p++)
> 	{
> 		scanf("%d %d",&n,&m);
> 		memset(xihuan,false,sizeof(xihuan));
> 		for(int i=1;i<=n;i++)
> 		{
> 			scanf("\n");
> 			for(int j=1;j<=m;j++)
> 			{
> 				scanf("%c",&c);
> 				if(c=='*') xihuan[i][j]=true;
> 			}
> 		}
> 		int ans=0;
> 		memset(dui,0,sizeof(dui));
> 		memset(dui1,0,sizeof(dui1));
> 		for(int i=1;i<=n;i++)
> 			for(int j=1;j<=m;j++)
> 				if(xihuan[i][j])
> 				{
> 					//printf("%d %d\n",i,j);
> 					if(zhao(i,j,i,j)) ans++;
> 				}
> 		for(int i=1;i<=n;i++)
> 			for(int j=1;j<=m;j++)
> 				if(xihuan[i][j] && dui[i][j]==0) ans++;
> 		printf("%d\n",ans);
> 	}
> }

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