글 읽기 - 6086 번 파이썬 질문입니다!

gilks11 3년 전 0

아래 소스코드로 작성을 했는데 질문 있습니다.

A B 12

A D 11

B D 3

B C 6

B F 9

B E 5

D E 9

E C 3

C F 8

E F 4

입력시 21로 나오는데

정답이 19라고 나와있어서 질문드립니다. 6086번 테스트는 통과했는데 19, 21 중 어느게 맞는건가요?...

밑에 fin = toNum('Z') 부분은 F로 바꾸고 했을 때 21이 나오게 됩니다.

from collections import deque

INF=9876543210
maxNum=52


def toNum(alpa):
    if ord(alpa)<=ord('Z'):
        return ord(alpa)-ord('A')
    else:
        return ord(alpa)-ord('a')+26

def findMin(node):
    global minFlow
    if node==0:
        return

    rest=c[prev[node]][node]-flow[prev[node]][node]
    if rest<minFlow:
        minFlow=rest
    findMin(prev[node])

def makeFlow(node):
    if node==0:
        return
    flow[prev[node]][node]+=minFlow
    flow[node][prev[node]]-=minFlow

    makeFlow(prev[node])

N=int(input())
graph={}
c=[[0 for j in range(maxNum)] for i in range(maxNum)]
flow=[[0 for j in range(maxNum)] for i in range(maxNum)]
totalFlow=0
fin=toNum('F')

for i in range(maxNum):
    graph[i]=[]

for i in range(N):
    a,b,cost=input().split()
    numA=toNum(a)
    numB=toNum(b)
    cost=int(cost)

    c[numA][numB] += cost
    c[numB][numA] += cost
    graph[numA].append(numB)
    graph[numB].append(numA)

while(1):
    prev=[-1 for i in range(maxNum)]
    q=deque([0])

    while(q):
        now=q.popleft()
        if now==fin:
            break

        for next in graph[now]:
            if (c[now][next]-flow[now][next])>0 and prev[next]==-1:
                q.append(next)
                prev[next]=now

    if prev[fin]==-1:
        break

    minFlow=INF
    findMin(fin)
    
    makeFlow(fin)

    totalFlow+=minFlow



print(totalFlow)

eschoo03 9달 전 0

고수는 아니지만 통과한 코드에 입력했을때 21이 나오네요 ㅎㅎ
저는

10
A B 12
A D 11
B D 3
B C 6
B Z 9
B E 5
D E 9
E C 3
C Z 8
E Z 4
21

이렇게 F를 Z로 바꿔서 입력했습니다 :D

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

문제

문제

출처

ICPC

6086 번 파이썬 질문입니다!

gilks11 3년 전 0

eschoo03 9달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말