💉質問内容

問題に答える

💉にゅうしゅつりょく

🧺入力
最初の行には、従業員数Nと作業数Mが与えられる.(1 ≤ N, M ≤ 1,000)
2行目からN行目のi行目には、i番の従業員ができることの数とできることの番号が与えられています.
🧺しゅつりょく
第1行は江湖の4つの会社ができることの個数を印刷します.

🔋サンプルI/O

🔮入力例1

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

🔮サンプル出力1

4

💉もんだいぶんせき

🔋ぶんかつ

DFS、二分整合、最大流量、ネットワーク流量

🔋難易度

プラチナIV

💉問題を解く

🔋解法

ただこのマッチング実装の問題は
このとき注意が必要なのはMが使えないことです
M個の仕事の中で一番大きいと思っていたので、M号を返してあげましたが、そうではありませんでした.(なんだっけ…?)

🔋ソースコード

#include <bits/stdc++.h>

constexpr int MAX = 1001;
constexpr int INF = 1e9+7;

std::vector<int> adj[MAX];

int d[MAX];
bool visit[MAX];

bool dfs(int current){
	for(int i=0;i<adj[current].size();++i){
		int next = adj[current][i];
		
		if(visit[next]) continue;
		visit[next] = true;
		
		if(d[next] == 0 || dfs(d[next])){
			d[next] = current;
			return true;
		}
	}
	
	return false;
}

int BipartiteMatching(int N){
	int count = 0;
	
	for(int i=1;i<=N;++i){
		memset(visit, false, sizeof(visit));
		if(dfs(i)) ++count;
	}
	
	return count;
}

int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	
	int N, M;
	
	std::cin >> N >> M;
	
	for(int i=1;i<=N;++i){
		int T;
		std::cin >> T;
		
		for(int j=0;j<T;++j){
			int a;
			std::cin >> a;
			
			adj[i].push_back(a);
		}
	}
	
	std::cout << BipartiteMatching(N);
}

NとMが紛らわしくて一度間違えた
4日以内に解決できるアルゴリズムの問題はははははは
最近はWebアプリケーションの開発に夢中で、アルゴリズムの問題はまったく解決されていません.
手を解くためにマッチング問題を解いた.
アプリケーションはコトリンを勉強しています.ホームページはhtml、css、js(jquery)などを勉強しています.
これからはWeb開発という感じでphpにも挑戦してみたいと思います…!
ゲーム、ネット、画像に精通する日まで!
(絵はもともと臭い手で、一生の夢はアニーを描くことです.それは可能ですか...ㅠㅠ)

💉終了時..。

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