글 읽기 - 로직에서 이상한부분이 있는지 잘모르겠습니다.

jerryprk 4년 전 0

view구문들은 주석처리하엿습니다

#ifdef _DEBUG
#include "bits_stdc++.h"
#else
#include "bits/stdc++.h"
#endif
#pragma warning(disable:4996)
using namespace std;

#define INF 2147483647
int people;
int lowcost = INF;
#define MAX 20
vector <int> v[MAX];
int region[MAX] = {};

bool rlist[MAX] = {};
int cal() {
	int red = 0, blue = 0;
	for (int i = 1; i <= people; i++) {
		if (rlist[i]) {
			red += region[i];
		}
		else blue += region[i];
	}
	//cout << red << "\t" << blue << endl;
	return abs(red - blue);
}
/*
void r_view() {
	for (int i = 1; i <= people; i++)
		if (rlist[i])
			cout << i << " ";
	cout << endl;
}
void c_view(bool check[]) {
	cout << "check list :\t";
	for (int i = 1; i <= people; i++)
		if (check[i])
			cout << i << " ";
	cout << endl;
}
*/
void solve(int len) {
	//r_view();
	bool check[MAX] = { 0, };
	queue <int> q;
	int cnt = 0;
	for (int i = 1; i <= people; i++) {
		if (!rlist[i] && !check[i]) {
			if (cnt > 1)return;
			cnt++;
			q.push(i);
			check[i] = true;
			//cout << "input :: " << i << "\t";
			//c_view(check);
			while (!q.empty()) {
				int out = q.front(); q.pop();
				for (int k = 0; k < v[out].size(); k++) {
					int next = v[out][k];
					if (!check[next] && !rlist[next]) {
						check[next] = true;
						q.push(next);
					}
				}
			}
		}
	}
	int result = cal();
	lowcost = lowcost < result ? lowcost : result;
}
void make(int start, int len, int cnt) {
	if (cnt == len) {
		solve(len);
		return;
	}
	for (int i = start + 1; i <= people; i++) {
		rlist[i] = true;
		make(i, len, cnt + 1);
		rlist[i] = false;
	}
}
int main() {
#ifdef _CONSOLE
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> people;
	for (int i = 1; i <= people; i++)
		cin >> region[i];
	int whole = 0, a = 0;
	for (int i = 1; i <= people; i++) {
		cin >> whole;
		for (int k = 1; k <= whole; k++) {
			cin >> a;
			v[i].push_back(a);
		}
	}

	for (int i = 1; i <= people; i++) {
		for (int k = 1; k <= people / 2; k++) {
			rlist[i] = true;
			make(i, k, 1);
			rlist[i] = false;
		}
	}
	if (lowcost == INF) {
		cout << "-1";
		return 0;
	}
	cout << lowcost;
}

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

문제

문제

출처

ICPC

로직에서 이상한부분이 있는지 잘모르겠습니다.

jerryprk 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말