낙 곡 P2770: 항공 노선 문제 [최대 비용 최대 흐름]

제목 설명
      항공 도 를 정 하고 그림 의 정점 은 도 시 를 대표 하 며 변 은 2 도시 간 의 직통 항 로 를 대표 한다.현재 다음 과 같은 제한 조건 을 만족 시 키 고 도 시 를 가장 많이 거 치 는 여행 노선 을 찾 아야 한다.
(1) 가장 서쪽 끝 도시 에서 출발 하여 서쪽 에서 동쪽 으로 몇 개의 도 시 를 거 쳐 가장 동쪽 끝 도시 에 도착 한 다음 에 동쪽 에서 서쪽 으로 출발점 으로 날 아 간다 (몇 개의 도 시 를 거 칠 수 있다).
(2) 출발점 도 시 를 제외 한 모든 도 시 는 1 회 만 방문 할 수 있다.
      주어진 항공 지도 에 대해 알고리즘 을 설계 하여 요 구 를 만족 시 키 는 가장 좋 은 항공 여행 노선 을 찾 아 보 세 요.
해제
      이 문 제 는 나의 이해 에 따 르 면 두 결점 과 꼬리 노드 를 포함 하 는 가장 큰 고 리 를 구 하 는 것 이다.
      그래서 우 리 는 이 고 리 를 두 개의 처음부터 끝까지 노드 의 경로 로 뜯 을 수 있다. 그러면 이 두 경로 의 길 이 를 - 2 최 장 으로 하면 된다.
      우리 좀 뜯 어 보 자. i 도 시 를 좀 뜯 어 보 자. ui, vi。그러면 x - > y 는 한 변 이 있 으 면 vy 방향 ux. 연 결 된 트 래 픽 은 INF 이 고 비용 은 0 의 변 이다. 가면 서 비용 을 소모 하지 않 기 때문이다.
      요구 가 가장 긴 만큼 우 리 는 원래 의 최소 비용 최대 흐름 에서 최대 비용 최대 흐름 으로 바 꿔 야 한다.
      SPFA 에서 가장 긴 길 을 구 할 때 어떻게 해 야 하 는 지 묻 고 싶 은 사람 이 있 을 것 이다. 간단 하 다. 우 리 는 변 권 을 마이너스 로 바 꾸 면 된다.
      각 점 의 입 점 ui. 점 마다 vi. 유량 은 1 이 고 비용 은 - 1 의 변 을 만 드 는 것 은 비행기 가 이 도시 에서 한 번 만 돌 수 있다 는 것 을 나타 낸다 (이 도 시 를 한 번 만 지나 갈 수 있다). 비용 총수 의 절대 치 는 바로 도시 총 수 를 거 치 는 것 이 므 로 2 를 줄 이 는 것 을 잊 지 말 아야 한다.머리 결점 과 꼬리 노드 는 모두 두 번 거 쳤 기 때문이다.
      그러나 1 과 n 의 이런 변 은 두 개 를 만들어 야 유량 을 나 눌 수 있 기 때문이다.
      begin 원점 에서 u1. 유량 이 2 이 고 비용 이 0 인 변 을 만 드 는 것 은 출발점 에서 종점 까지 의 경 로 를 찾 아야 한 다 는 뜻 이다.
      v_n. end 외환 점 에 유량 이 2 이 고 비용 이 0 인 변 을 만 드 는 것 은 같은 이치 이다.
아래 의 상황 은 특 판 해 야 한다.
1. 최 동단 도시 와 최 서 단 도시 만 지나 고 빼 지 않 아 도 된다 2.
2. dfs 에서 답 을 출력 할 때 이 변 이 지나 간 것 인지 아 닌 지 판단 근 거 를 잘 파악 하 세 요.
코드 가 좀 못 생 겼 는데, 주로 생각 을 파악 하 는 거 야.

#include 
#include 
#include 
#include