algorithm Study/2014/virtual

• 기본적인 아이디어는 노드를 하나씩 제거하는 것
  
  • 루프가 없고 한 방향으로만 흘러가기 때문에 가능
    
• 들어오는 edge가 없는 node를 제거하고 그 node에서 나가는 edge와 연결된 node들의 최대 흐를 수 있는 양을 확인 후 변경
  
  • 현재 node에서 흐를 수 있는 양보다 크면 그 양을 갱신하고 parent를 이전 노드로 지정
    
  • 같아도 변경하지 않음.
    
    • 최대로 흐를 수 있는 양이 같더라도 먼저 계산한 것이 더 최단거리임
      
• path는 도착지점부터 parent 노드를 쫒아가면 됨.
  

• 처음에는 하나씩 지워나간다고 생각해서 검사할 node를 int 형으로 기록했으나, 가장 초기에는 지워야 하는 node가 시작점 하나만 있는 것이 아닌 것을 알게 되어 stack으로 변경.
  

• Python2
  
• http://183.106.113.109/displaysrc.php?id=1178830
  

points = int(raw_input())
point_current, point_end = [int(i) for i in raw_input().split()]
 
graph = [[-1] * (points + 1) for i in range(points + 1)]
point_in = [0] * (points + 1)
point_parent = [0] * (points + 1)
point_parent[point_current] = -1
point_flow = [0] * (points + 1)
point_flow[point_current] = 99999
 
while True:
    try:
        input_data = [int(i) for i in raw_input().split()]
        if not input_data:
            break
        graph[input_data[0]][input_data[1]] = input_data[2]
        point_in[input_data[1]] += 1
    except EOFError:
        break
 
stack = [point_current]
for i in range(1, points + 1):
    if point_in[i] == 0 and i != point_current:
        stack.append(i)
 
while stack:
    point_current = stack.pop()
    for i in range(points + 1):
        flow = min(graph[point_current][i], point_flow[point_current])
        if flow != -1:
            graph[point_current][i] = -1
            if flow > point_flow[i]:
                point_flow[i] = flow
                point_parent[i] = point_current
            point_in[i] -= 1
            if point_in[i] == 0:
                stack.append(i)
 
print point_flow[point_end]
 
path = []
point_current = point_end
while point_current != -1:
    path.append(point_current)
    point_current = point_parent[point_current]
 
path.reverse()
for i in path:
    print i,

• Network Flow 문제로 나와있는데, 그냥 적절한 가지치기를 통해서 dfs로 경로를 탐색해나가도 될 것 같음. n도 100밖에 안되고, 인접행렬 대신에 인접리스트를 사용해서 적당하게 Search Space를 줄이면 시간 안에 답이 나올 것 같음.
  
  
• SP - 시작점, DP - 도착점, answer - SP에서 DP까지 경로의 최소 Cost.
  
• SP에서 DP까지 가는 경로를 찾는 것은 DP에서 SP까지 가는 경로를 찾는 것과 같음.
  
• Stack에 담을 거니까 그냥 DP에서 SP까지 가는 경로를 찾자.
  
• 가지 치기 방법 : 내가 지금까지 구한 answer보다, 다른 노드로 연결 되는 Edge의 Cost가 작으면 탐색 할 필요가 없음.
  

• 오랜만에 C++로 짜볼까하고 시작했을 때부터 비극은 시작되었음.
  
• 문제 푸는데 집중을 해야하는데 변수 이름, 클래스 이름에 신경을 많이 쓰게됨. 그렇다고 코드가 이쁘지도 않음.
  
• 첫 시도, 시간 초과.
  
• 첫 번째 해결방법 : 다음 노드로 가는데 Cost가 높은 edge부터 탐색하자. adjList를 정렬함.
  - 여전히 시간 초과
  
• 두 번째 해결방법 : 소스를 보던 중, 의도했던 가지치기 코드가 잘못되었음을 발견.