アルゴリズム問題解決Back-1043 C++

21629 ワード
テキストリンク
🎲質問する
住所:白駿1043
志敏はパーティーに行っておしゃべりをするのが好きだ.パーティーに行くたびに、志敏は志敏の大好きな話をします.志敏がその話をするときは、そのまま本当のことを言うか、大げさに言うか.もちろん大げさに言うのはずっと面白いので、できるだけ大げさに言う.しかし、志敏は詐欺師と思われたくない.問題はその物語の真相を知っている人がいることだ.そのため、彼らがパーティーに来たとき、志敏は真実を言うしかなかった.もちろん、あるパーティーで真実を聞いたり、別のパーティーで大げさな話を聞いたりすると、志敏も詐欺師だと思われます.志敏のようなことは避けなければならない.
人の数Nを与える.そしてその物語の真相を知っている人がいます.そしてパーティーごとに来た人の番号をあげます.志敏はすべてのパーティーに参加します.このとき、智旻が詐欺師とは思えないが、大げさな話ができるチームの数の最高値を求めるプログラムを作成してください.
入力
1行目は人の数Nとチームの数Mを与える.
2行目は物語の真相を知っている人数と番号を示した.まず真実を知っている人の数を与え、その数に基づいて人の番号を与える.人々の番号は1からNまでの数字です.
3行目から、M行は同じように各チームの人数と番号を与える.
N,Mは50以下の自然数であり,真実を知る人数は0以上50以下の整数であり,各チームが来る人数は1以上50以下の整数である.
のり付け
解答方法
入力値が小さいため、時間はほとんど制限されません.bfsのような方法で解決した.キューに初期の真実を知っている人の番号を入れ、繰り返し文を返します.キューに真実を知っている人がいる場合は、チェックした番号かどうかをチェックし、キューに入れます.Q祈願まで繰り返し、誰も真実を知らないパーティーをプリントアウト.

  • NとMは、真実を知っている人の数、情報を入力する際に、真実を知っている人の数をQに押し上げます.

  • チーム全体の情報を配列に入力します.
    void init() {
	cin >> N >> M >> tmp;
	
	for (int i = 0; i < tmp; i++) {
		int num;
		cin >> num;
		q.push(num);
	}
	for (int i = 1; i <= M; i++) {
		int num;
		cin >> num;
		for (int j = 0; j < num; j++) {
			cin >> tmp;
			party[i][tmp] = true;
		}
	}
}

  • ループwhile文を生成し、Qリクエストまでキューの先頭の数字(真実を知っている人)がキューに存在する場合、そのキューにキューを追加したすべての人の中で、真実を知らない人に限られる.

  • 未使用のチームの0番インデックスに対してtrue処理を行い,既に巡回チームであることを示す.

  • 最後に、キューの一番前の部分をポップアップし、キューが要求されるまで繰り返します.

  • チーム全体の0番目のインデックスがfalseの場合、出力をカウントします.
    void solve() {
	while (!q.empty()) {
		for (int i = 1; i <= M; i++) {
			if (party[i][0] == false && party[i][q.front()] == true) {
				party[i][0] = true;
				visited[q.front()] = true;

				for (int k = 1; k <= N; k++) {
					if (party[i][k] == true && visited[k] == false) {
						q.push(k);
					}
				}
			}
		}
		q.pop();
	}
	
	for (int i = 1; i <= M; i++) {
		if (party[i][0] == false) {
			result++;
		}
	}
	cout << result;
}
    • 完全なコード
    #include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

int M, N;
int tmp, result = 0;
bool party[51][51] = { 0, };
bool visited[51] = { 0, };
queue<int> q;

void init();
void solve();

void init() {
	cin >> N >> M >> tmp;
	
	for (int i = 0; i < tmp; i++) {
		int num;
		cin >> num;
		q.push(num);
	}
	for (int i = 1; i <= M; i++) {
		int num;
		cin >> num;
		for (int j = 0; j < num; j++) {
			cin >> tmp;
			party[i][tmp] = true;
		}
	}
}

void solve() {
	while (!q.empty()) {
		for (int i = 1; i <= M; i++) {
			if (party[i][0] == false && party[i][q.front()] == true) {
				party[i][0] = true;
				visited[q.front()] = true;

				for (int k = 1; k <= N; k++) {
					if (party[i][k] == true && visited[k] == false) {
						q.push(k);
					}
				}
			}
		}
		q.pop();
	}
	
	for (int i = 1; i <= M; i++) {
		if (party[i][0] == false) {
			result++;
		}
	}
	cout << result;
}

int main() {
	init();
	solve();
	return 0;
}
    Githubアクションによる記事の連続配信
    生産性2021のためのREADME