BOJ-17199 Milk Factory(C++)

8128 ワード
テキストリンク
質問元:https://www.acmicpc.net/problem/17199
問題の難易度
Silver 1
問題の処理方法
1番からN番まで、入力値が示す方向は一方向で、1局を双方向化すれば突き当たりまで行けます.しかし,この場合の問題は出力最小値係数である.
パスコード
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define INF 987654321

using namespace std;

int arr[101][101];

int main() {
	int N;
	cin >> N;
	
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		arr[a][b] = 1;
	}
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (arr[i][k] == 1 && arr[k][j] == 1) arr[i][j] = 1;
			}
		}
	}
	int res = INF;
	for (int i = 1; i <= N; i++) {
		int cnt = 0;
		for (int j = 1; j <= N; j++) {
			if (arr[j][i] == 1) cnt++;
		}
		if (cnt == N - 1) {
			res = i;
			break;
		}
	}
	res = res == INF ? -1 : res;
	cout << res;

	return 0;
}
フィードバック
最初の質問は英語ですか?説明にも時間がかかりました....1番からN番までは接続が見つかればいいと思っていたのでDaestraと似たような形をしていましたが、間違えました!一方通行であることは確認できなかったが、その後N値も小さく時間制限が2秒であることを考慮し、フロイドとシエルの方法を思いついた.
[Programmers]-中性化の有無を理解する
エリキシルにおけるDYP‐A 01超音波距離センサの使用