글 읽기 - 중간이 될수 없음을 판단하는 방법에 대한 질문입니다.

dladydwo123 5년 전 0

A보다 무거운 노드가 mid개 이상 있거나, 가벼운노드가 mid개 이상 있으면 중간이 될수 없다고 생각했는데, 이 논리가 맞나요?

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<set>
#include<iostream>
#define ll long long
#define ull unsigned long long
using namespace std;

int min(int a, int b) {
	if (a < b) return a;
	return b;
}

int max(int a, int b) {
	if (a > b) return a;
	return b;
}

int N, M;
int map[100][100] = { 0, };

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d %d", &a, &b); //a가 b보다 무겁다
		map[a][b] = 1; //a가 b보다 무겁다.
		map[b][a] = -1; //b가 a보다 가볍다
	}
	for (int j = 1; j <= N; j++)
		for (int k = 1; k <= N; k++)
			for(int i=1; i<= N; i++)
				if (map[j][k] != 0 && map[j][k] == map[k][i])
					map[j][i] = map[k][i];
	
	int ret = 0;
	int mid = (N + 1) / 2;
	for (int i = 1; i <= N; i++) {
		int min_count = 0;
		int max_count = 0;
		for (int j = 1; j <= N; j++) {
			if (map[i][j] == -1)
				min_count += 1;
			else if (map[i][j] == 1)
				max_count += 1;
		}
		if (min_count >= mid)
			ret += 1;
		else if (max_count >= mid)
			ret += 1;
	}
	printf("%d", ret);
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

중간이 될수 없음을 판단하는 방법에 대한 질문입니다.

dladydwo123 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말