P1894 - histcat

P1894

Oct 13, 2023#oi4

AI Translation

This post is translated from Chinese into English through AI.View Original

AI-generated summary

The document discusses a problem related to maximizing the allocation of cows to stalls, where each cow can only be associated with one stall. It suggests using a bipartite graph to solve the problem. The provided C++ code implements a maximum matching algorithm for a bipartite graph, utilizing depth-first search (DFS) to find matches. The main function reads the number of cows and stalls, builds the graph, and calculates the maximum number of matches, which is then printed as the result.

Problem#

link

Solution#

Since each cow only has a relationship with the barn, we want to find out how many barns can be allocated at most, so we can establish a bipartite graph.

Code#

// Bipartite graph maximum matching
#include<bits/stdc++.h>

using namespace std;

const int N = 510;
int head[N], nxt[50010], to[50010], cnt = 1;
int n, m, e;

void add(int x, int y)
{
	to[++cnt] = y;
	nxt[cnt] = head[x];
	head[x] = cnt;
}

int vistime[N], match[N];

bool dfs(int u, int vist)
{
	if(vistime[u] == vist) return 0; // If it forms a cycle, it cannot be matched
	vistime[u] = vist;

	for(int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		if(match[v] == 0 || dfs(match[v], vist))
		{
			match[v] = u;
			return true;
		}
	}
	return 0;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for(int i = 1, v, s; i <= n; i++)
	{
		cin >> s;
		for(int j = 1; j <= s; j++)
		{
			cin >> v;
			add(i, v);
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++)
	{
		if(dfs(i, i))
		{
			ans++;
		}
	}
	cout << ans;
	return 0;
}