💉質問内容

問題に答える

💉にゅうしゅつりょく

🧺入力
1行目は牛の数Nと畜舎の数Mを与える.(1 ≤ N, M ≤ 200)
2行目からN行に各要素が加えたい祝辞の情報が与えられる.i最初の牛が入ることを希望する畜舎の数Si(0≦Si≦M)を与え、次いで6個の畜舎番号を与える.同じ祝辞番号は2回以上与えられなかった.
🧺しゅつりょく
1行目の出力は畜舎に入ることができる牛の最値です.

🔋サンプルI/O

🔮入力例

5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

🔮サンプル出力

4

💉もんだいぶんせき

🔋ぶんかつ

ネットワークトラフィック、最大トラフィック、二分整合

🔋難易度

プラチナIV

💉問題を解く

🔋解法

一般的な二分整合問題
特に注意することはありません.

🔋ソースコード

#include <bits/stdc++.h>

//Static variables
constexpr int MAX = 201;
constexpr int INF = 987654321;

//AlgoCapsule
class AlgoCapsule {
public:
	void Run() {
		Input();
		Solve();
		Output();
	}

	void Input() {
		std::cin >> N >> M;

		for (int i = 1; i <= N; ++i) {
			int T;
			std::cin >> T;
			for (int k = 0; k < T; ++k) {
				int a;
				std::cin >> a;
				adj[i].push_back(a);
			}
		}
	}

	void Solve() {
		for (int i = 1; i <= N; i++) {
			std::fill(visit, visit + MAX, false);
			if (BipartiteMatching(i)) count++;
		}
	}

	void Output() {
		std::cout << count;
	}

	bool BipartiteMatching(int start) {
		for (int i = 0; i < adj[start].size(); ++i) {
			int x = adj[start][i];

			if (visit[x]) continue;
			visit[x] = true;

			if (d[x] == 0 || BipartiteMatching(d[x])) {
				d[x] = start;
				return true;
			}
		}
		return false;
	}

	AlgoCapsule() { }
private:
	bool visit[MAX];
	int d[MAX];
	std::vector<int> adj[MAX];
	int N, M, count = 0;
};

//Module Entry
int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);

	AlgoCapsule AC;
	AC.Run();

	return 0;
}

低コストアルゴリズムを使用して問題に答えるデフォルトのソースコードは初めてです.
アルゴリズムの問題を解くためのデフォルトのソースコードの表示
このマッチング問題についてはあまりやったことがないので、初めてこのマッチング問題を作った人にとってはいい問題です.

💉終了時..。

気になる部分があればコメントで質問しましょう~