글 읽기 - 8%정도에서 틀리네요ㅠㅠ 유니온파인드

chae01122 2년 전 0

조합과 유니온 파인드를 사용해서 풀었는데 8프로 정도에서 틀리네요ㅠㅠ 반례가 있을까요?

아니면 유니온 파인드로 풀 수 없는 이유라도 있나요?

#include <bits/stdc++.h>

using namespace std;

const int MN = 12;
const int INF = 1e9;

int arr[MN];

vector<int> v[MN];
set<int> s[MN];
int ans=INF; 

int top=0;
int D[MN];

int N;

int par[MN];
int rnk[MN];

void init(){
	for(int i=0; i<MN; i++){
		par[i] = i;
		rnk[i] = 1;
	}
}


int find(int x){
	if(x == par[x]) return x;
	return par[x] = find(par[x]);
}

void Union(int x, int y){
	x = find(x);
	y = find(y);
	
	if(x==y) return;
	
	if(rnk[x]<rnk[y]) swap(x,y);
	par[y] = x;
	
	if(rnk[x] == rnk[y]) rnk[x]++;
}

void check(){
	vector<int> v1;
	vector<int> v2;
	int idx=0;
	
	// 조합으로 나누어진 두 구역의 번호를 따로 저장. 
	for(int i=1; i<=N; i++){
		if(i == D[idx]){
			v1.push_back(i);
			idx++;
		}
		else{
			v2.push_back(i);
		}
	}
	
	//연결되어 있으면 union 
	for(int i=0; i<v1.size(); i++){
		for(int j=i+1; j<v1.size(); j++){
			if(s[v1[i]].find(v1[j]) != s[v1[i]].end()){
				
				Union(v1[i],v1[j]);
			}
		}
	}

	int par1 = par[v1[0]];
	int sum1 = arr[v1[0]];
	
	//만약 모두 연결되어 있으면 sum1에 인구 수 누적 저장 연결되어 있지 않으면 종료  
	for(int i=1; i<v1.size(); i++){
		if(par1 != par[v1[i]]) return;
		sum1+=arr[v1[i]];
	}
	
	//연결되어 있으면 union 
	for(int i=0; i<v2.size(); i++){
		for(int j=i+1; j<v2.size(); j++){
			if(s[v2[i]].find(v2[j]) != s[v2[i]].end()){
				Union(v2[i],v2[j]);
			}
		}
	}
	//만약 모두 연결되어 있으면 sum2에 인구 수 누적 저장 연결되어 있지 않으면 종료
	int par2 = par[v2[0]];
	int sum2 = arr[v2[0]];
	for(int i=1; i<v2.size(); i++){
		if(par2 != par[v2[i]]) return;
		sum2+=arr[v2[i]];
	}

	int res = abs(sum1-sum2);
	
	ans = min(res,ans);
	
}

void combination(int start, int end){
	if(top == end){
		init();
		check();
		return;
	}
	
	for(int i=start; i<=N; i++){
		D[top++] = i;
		combination(i+1,end);
		top--;
	}
}



int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	
	cin>>N;
	for(int i=1; i<=N; i++){
		cin>>arr[i];
	}
	
	for(int i=1; i<=N; i++){
		int n;
		cin>>n;
		for(int j=0; j<n; j++){
			int tmp;
			cin>>tmp;
			s[i].insert(tmp);
		}
	}
	
	int c = N/2;
	
	for(int i=1; i<=c; i++){
		top=0;
		memset(D,0,sizeof(D));
		combination(1,i); //모든 조합에 대하여 경우의 수를 구한다. 
	}
	
	if(ans != INF) cout<<ans<<'\n';
	else cout<<-1<<'\n';
	
	return 0;
	
}

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

문제

문제

출처

ICPC

8%정도에서 틀리네요ㅠㅠ 유니온파인드

chae01122 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말