P1894 - histcat

P1894

2023年10月13日#oi4

AI 翻訳

この記事はAIを通じて中国語から日本語に翻訳されました。原文を表示

AI が生成した要約

この文書は、牛と牛舎の関係を最大化するための問題について説明しています。各牛は特定の牛舎としか関係を持たないため、二分グラフを用いて最大マッチングを求めるアプローチが提案されています。コードはC++で書かれており、牛舎の数と牛の数を入力として受け取り、最大のマッチング数を計算して出力します。具体的には、深さ優先探索（DFS）を用いてマッチングを行い、最終的な結果を表示します。

問題#

link

解説#

各牛は牛舎との関係しか持たないため、最大でいくつの牛舎に割り当てられるかを求めることができるので、二部グラフを構築できます。

コード#

//二部グラフ最大マッチング
#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;//サイクルができたらマッチングできない 
	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;
}