글 읽기 - 도움 부탁드립니다

djh20 3년 전 0

벨만 포드를 모른채 풀어서 우선 문제를 보고 풀었습니다.
질문글에 있는 몇 없는 반례들도 잘 돌아가는 것 같은데 왜 실패가 나오는지 모르겠네요..
도움 부탁드립니다

.
﻿
import javafx.util.Pair;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader <i>br </i>= new BufferedReader(new InputStreamReader(System.<i>in</i>));

    public static void main(String[] args) throws IOException {
        int numTest = Integer.<i>parseInt</i>(<i>br</i>.readLine());

        for(int i = 0 ; i < numTest ; i++){
            <i>testCase</i>();
        }
    }

    private static void testCase() throws IOException {
        StringTokenizer st = new StringTokenizer(<i>br</i>.readLine());
        int numEdge = Integer.<i>parseInt</i>(st.nextToken());
        int numVertex = Integer.<i>parseInt</i>(st.nextToken());
        int numHole = Integer.<i>parseInt</i>(st.nextToken());

        ArrayList<Pair<Integer,Integer>> graph[] = new ArrayList[numEdge+1];
        <i>initGraph</i>(graph);

        for(int i = 0 ; i < numVertex ; i++){
            StringTokenizer st2 = new StringTokenizer(<i>br</i>.readLine());
            int s = Integer.<i>parseInt</i>(st2.nextToken());
            int g = Integer.<i>parseInt</i>(st2.nextToken());
            int w = Integer.<i>parseInt</i>(st2.nextToken());
            graph[s].add(new Pair(g,w));
            graph[g].add(new Pair(s,w));
        }
        ArrayList<Integer> holeEdges = new ArrayList<>();
        for(int i = 0 ; i < numHole ; i++){
            StringTokenizer st3 = new StringTokenizer(<i>br</i>.readLine());
            int s = Integer.<i>parseInt</i>(st3.nextToken());
             int g = Integer.<i>parseInt</i>(st3.nextToken());
            int w = Integer.<i>parseInt</i>(st3.nextToken())*-1;
            holeEdges.add(s);
            graph[s].add(new Pair(g,w));
        }
        for(int i = 1 ; i < graph.length ; i++){
            Collections.<i>sort</i>(graph[i], new Comparator<Pair<Integer, Integer>>() {
                @Override
                public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
                    return Integer.<i>compare</i>(o1.getValue(),o2.getValue())*-1;
                }
            });
        }
        boolean flag = false;
        for(int i = 0 ; i < holeEdges.size() ; i++){
            int holeNo = holeEdges.get(i);
            Stack<Pair<Integer,Integer>> queue = new Stack<>();
            Stack<Integer> pre = new Stack<>();
            pre.push(0);
            queue.add(new Pair(holeNo,0));
            int tree[] = new int[numEdge+1];
            <i>initTree</i>(tree);

            while(!queue.isEmpty()){
                Pair<Integer,Integer> pair = queue.pop();
                int s = pair.getKey();
                int w = pair.getValue();
                int p = pre.pop();
                if(<i>union</i>(p, s, tree)){
                    for (int j = 0; j < graph[s].size(); j++) {
                        Pair<Integer, Integer> next = graph[s].get(j);
                        queue.add(new Pair(next.getKey(), w + next.getValue()));
                        pre.push(s);
                    }
                }else{
                    if(s == holeNo){
                        if(w < 0){
                            flag = true;
                            break;
                        }
                    }
                }

                if(flag)
                    break;
            }
        }
        if(flag)
            System.<i>out</i>.println("YES");
        else
            System.<i>out</i>.println("NO");
    }


    private static boolean union(int s, int g, int[] tree) {
        int sParent = <i>find</i>(s,tree);
        int gParent = <i>find</i>(g,tree);

        if(sParent == gParent)
            return false;
        else{
            tree[sParent] = gParent;
            return true;
        }
    }

    private static int find(int x, int[] tree) {
        if(tree[x] == x)
            return x;
        else
            return tree[x] = <i>find</i>(tree[x], tree);
    }

    private static void initTree(int[] tree) {
        for(int i = 0 ; i < tree.length ; i++){
            tree[i] = i;
        }
    }

    private static void initGraph(ArrayList<Pair<Integer, Integer>>[] graph) {
        for(int i = 0 ; i < graph.length ; i++){
            graph[i] = new ArrayList<>();
        }
    }
}

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

문제

문제

출처

ICPC

도움 부탁드립니다

djh20 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말