글 읽기 - 아 도저히 뭐가 잘못됐는지 잘 모르겠습니다.

yujun93 2년 전 0

반례 틀린거 뭔지는 알겠으나 비트마스킹으로 풀려고하니까 뭐가 미스난건지 못찾겠습니다 ㅠㅠ

어떻게 풀어야 잘 풀었다고 소문날지 ... 다시 답을 찾아봐야하는

package main;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    private static int[] arr, parent;
    private static int N, bitN = 0, min = Integer.MAX_VALUE;
    private static ArrayList<Integer> bitList = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter wt = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(rd.readLine());
        StringTokenizer st = new StringTokenizer(rd.readLine());
        arr = new int[N + 1];
        parent = new int[N + 1];
        int idx = 1;

        for (int i = 1; i <= N; i++) {
            bitN |= (1 << i);
            parent[i] = i;
        }

        while (st.hasMoreTokens()) {
            arr[idx++] = Integer.parseInt(st.nextToken());
        }

        bitList.add(0);

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(rd.readLine());
            int n = Integer.parseInt(st.nextToken());
            int num = 1 << i;

            while (st.hasMoreTokens()) {
                int z = Integer.parseInt(st.nextToken());
                num |= (1 << z);
                union(i, z);
            }

            bitList.add(num);
        }

        long count = Arrays.stream(parent).distinct().count();

        if (count <= 3) {
            back(0, 1);
        }

        if (min == Integer.MAX_VALUE) {
            wt.write("-1");
        } else {
            wt.write(String.valueOf(min));
        }

        wt.flush();
        wt.close();
    }

    public static int find(int a) {
        if (parent[a] == a) return a;

        return parent[a] = find(parent[a]);
    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a != b) {
            parent[b] = a;
        }
    }

    public static void back(int bit, int at) {
        if (Integer.bitCount(bit) <= N / 2 && Integer.bitCount(bit) > 0) {
            int sum1 = 0, sum2 = 0;
            int reverse = bitN ^ bit;
            boolean check = true;

            for (int i = 1; i <= N; i++) {
                if (((1 << i) & bit) != 0) {
                    if (Integer.bitCount(bit) > 1 && Integer.bitCount(bitList.get(i) & bit) == 1) {
                        check = false;
                        break;
                    }

                    sum1 += arr[i];
                } else {
                    if (Integer.bitCount(reverse) > 1 && Integer.bitCount(bitList.get(i) & reverse) == 1) {
                        check = false;
                        break;
                    }

                    sum2 += arr[i];
                }
            }

            if (check) {
                if (sum1 < sum2) {
                    min = Math.min(min, sum2 - sum1);
                } else {
                    min = Math.min(min, sum1 - sum2);
                }
            }
        } else if (Integer.bitCount(bit) > N / 2) {
            return;
        }

        for (int i = at; i <= N; i++) {
            bit |= (1 << i);
            back(bit, i + 1);
            bit -= (1 << i);
        }
    }
}

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

문제

문제

출처

ICPC

아 도저히 뭐가 잘못됐는지 잘 모르겠습니다.

yujun93 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말