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

匈牙利算法 844MS

Posted by ACAccepted at 2019-01-18 16:24:45 on Problem 1469 and last updated at 2019-01-18 16:26:00
#include <cstdio>
#include <bitset>
#include <cstring>
using namespace std;
int n,p,id;

struct edge
{
	int v,nx;
}set[300005];
int head[305],match[305];
bitset<105> chk;

void Addedge(int u,int v)
{
	id++;set[id].v=v;set[id].nx=head[u];
	head[u]=id;
}

bool dfs(int u)
{
	for(int k=head[u];k>0;k=set[k].nx)
		if(!chk[set[k].v])
		{
			chk[set[k].v]=true;
			if((match[set[k].v]==0)||dfs(match[set[k].v]))
			{
				match[set[k].v]=u;return true;
			}
		}
	return false;
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("courses.in","r",stdin);
	freopen("courses.out","w",stdout);
	#endif
	int cas=0;scanf("%d",&cas);
	while(cas--)
	{
		id=0;
		memset(match,0,sizeof(match));
		memset(head,-1,sizeof(head));
		int knum,stu;
		scanf("%d%d",&p,&n);
		for(int i=1;i<=p;i++)
		{
			scanf("%d",&knum);
			for(int j=1;j<=knum;j++)
			{
				scanf("%d",&stu);
				Addedge(stu,i);
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			chk.reset();
			if(dfs(i))ans++;
		}
		if(ans==p)puts("YES");
		else puts("NO");
	}
	fclose(stdin); fclose(stdout);
	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