글 읽기 - 반례가 뭘까요? ㅠ

jamescsi 6년 전 0

제가 해보는것들은 다 통과하는데...반례를 도저히 모르겠네요 ㅠㅠ

1%도 통과못하고 바로 틀렸습니다 뜨는데... 이유가 뭘까요? 미리 감사합니다

import java.util.*;

public class Main { 
	static int[][] graph;
	static int inf = 1001;
	static boolean[] visited;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		graph = new int[52][52];
		visited = new boolean[52];
		sc.nextLine();
		for(int i=0; i<n; i++) {
			String tmp = sc.nextLine();
			String[] s = tmp.split(" ");
			int a = convertToInt(s[0].charAt(0));
			int b = convertToInt(s[1].charAt(0));
			int cap = Integer.parseInt(s[2]);
			graph[a][b]=cap;
			graph[b][a]=0;
		}
		int ans = 0;
		while(true){
			Arrays.fill(visited, false);
			int flow = dfs(0, inf);
			if(flow==0) break;
			ans += flow;
		}
		System.out.println(ans);
	}
	public static void printGraph() {
		for(int i=0; i<graph.length; i++) {
			System.out.println();
			for(int j=0; j<graph[0].length; j++) {
				System.out.print(graph[i][j] +"   ");
			}
		}
	}
	public static int dfs(int from, int capacity) {
		if(from==25) {
			//System.out.print((char)(from+'A')+" ");
			return capacity;
		}
		
		visited[from] = true;
		for(int next=0; next<52; next++) {
			if(graph[from][next]<=0||visited[next]) {
				continue;
			}
			//System.out.print((char)(from+'A')+" ");
			int flow = dfs(next, Math.min(capacity, graph[from][next]));
			if(flow>0) {
				graph[from][next] -= flow;
				graph[next][from] += flow;
				return flow;
			}
		}
		
		return 0;
	}
	
	public static int convertToInt(char c) {
		if(c>='A'&&c<='Z') {
			return c-'A';
		}
		else {
			return c-'a'+26;
		}
	}
	
	
}

sgchoi5 6년 전 0

http://gooddaytocode.blogspot.... 대회 데이터 한 번 써보시지요.. : ) 배움이 짧아서... 이 정도 링크만..

jamescsi 6년 전 1

감사합니다~~ 슬랙에서 어떤분이 도와주셔서 해결됐어요. 처음에 입력받을 때 인접행렬에 같은 간선에 대한 데이터를 누적을 안한것때문에 그렇더라구요.

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

문제

문제

출처

ICPC

반례가 뭘까요? ㅠ

jamescsi 6년 전 0

sgchoi5 6년 전 0

jamescsi 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말