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

Floyd+匈牙利算法

Posted by xzy_xzy at 2019-01-20 14:59:46 on Problem 2594
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,id;
int match[505];
bool g[505][505],chk[505];

void init()
{
	memset(g,0,sizeof(g));
	int u,v;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		g[u][v]=1;
	}
}

void Floyd()
{
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(g[i][k]&&g[k][j])g[i][j]=1;
}

bool dfs(int x)
{
	for(int y=1;y<=n;y++)
		if(g[x][y]&&!chk[y])
		{
			chk[y]=true;
			if((match[y]==0)||dfs(match[y]))
			{
				match[y]=x;return true;
			}
		}
	return false;
}

int get_ans()
{
	memset(match,0,sizeof(match));
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		memset(chk,0,sizeof(chk));
		if(dfs(i))ans++;
	}
	return ans;
}

int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		if(n==0&&m==0)break;
		init();
		Floyd();
		printf("%d\n",n-get_ans());
	}
	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