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

先匹配 在枚举点 为什么wa

Posted by cycpp at 2009-10-06 14:45:54 on Problem 2125
#include <iostream>
using namespace std;
#define MN 1005
bool graph[MN][MN];//graph[x][y]
int  yMatch[MN], xMatch[MN];
bool vis[MN];
int  nx, ny;
int dfs(int v)
{
	int i;
	for(i=1; i<=ny; i++)
		if( graph[v][i] &&!vis[i])
		{
			vis[i]=true;
			if( yMatch[i]==0 || dfs(yMatch[i]))  
			{
				yMatch[i]=v;
				xMatch[v]=i;
				return 1;
			}
		}	
		return 0;
}
int maxMatch()
{	
	int i, ans=0;
	memset(yMatch, 0, sizeof(yMatch));
	memset(xMatch, 0, sizeof(xMatch));
	for(i=1; i<=nx; i++)
	{
		memset(vis, false, sizeof(vis));
		ans+=dfs(i);
	}
	return ans;
}
int g[MN][MN];
int aa[MN],bb[MN];
int n;
int pu[MN];
int main()
{
	int m;
	cin>>n>>m;
	int i;
	for(i=1;i<=n;++i)cin>>aa[i];
	for(i=1;i<=n;++i)cin>>bb[i];
	memset(g,0,sizeof(g));
	while(m--)
	{
		int s,t;
		cin>>s>>t;
		g[s][t]++;
	}
	int j;
	memset(graph,0,sizeof(graph));
	for(i=1;i<=n;++i)
	{
		for(j=1;j<=n;++j)
		{
			if(g[i][j])graph[i][j]=true;
		}
	}
	nx=ny=n;
	int mm=maxMatch();
	int f=0,ans=0;
	for(i=1;i<=n;++i)
	{
		if(bb[i]<aa[xMatch[i]])
		{
			pu[f++]=-i;
			ans+=bb[i];
		}
		else
		{
			pu[f++]=xMatch[i];
			ans+=aa[xMatch[i]];
		}
	}
	cout<<ans<<endl<<mm<<endl;
	for(i=0;i<f;++i)
	{
		if(pu[i]>0)
		{
			cout<<pu[i]<<" +\n";
		}
		else
		{
			cout<<-pu[i]<<" -\n";
		}
	}
	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