로 곡 P2770 항공 노선 문제

제목 설명
항공 도 를 정 하고 그림 의 정점 은 도 시 를 대표 하 며 변 은 2 도시 간 의 직통 항 로 를 대표 한다.현재 다음 과 같은 제한 조건 을 만족 시 키 고 도 시 를 가장 많이 거 치 는 여행 노선 을 찾 아야 한다.
(1) 가장 서쪽 끝 도시 에서 출발 하여 서쪽 에서 동쪽 으로 몇 개의 도 시 를 거 쳐 가장 동쪽 끝 도시 에 도착 한 다음 에 동쪽 에서 서쪽 으로 출발점 으로 날 아 간다 (몇 개의 도 시 를 거 칠 수 있다).
(2) 출발점 도 시 를 제외 한 모든 도 시 는 1 회 만 방문 할 수 있다.
주어진 항공 도 에 대해 알고리즘 을 설계 하여 요 구 를 만족 시 키 는 가장 좋 은 항공 여행 노선 을 찾 아 보 세 요.
입 출력 형식
입력 형식:
1 행 에는 2 개의 정수 N 과 V 가 있 고 N 은 도시 수 를 나타 내 며 N < 100, V 는 직항 노선 수 를 나타 낸다.다음 N 행 의 모든 줄 은 도시 이름 으로 비행 기 를 타고 이 도 시 를 방문 할 수 있다.도시 명 이 나타 나 는 순 서 는 서쪽 에서 동쪽 이다.즉, i, j 는 도시 표 열 에 도시 가 나타 난 순서 로 i > j 일 때 도시 i 가 도시 j 의 동쪽 에 있 고 두 도시 가 같은 경선 에 있 지 않다 는 것 을 나타 낸다.도시 이름 은 길이 가 15 를 넘 지 않 는 문자열 로 문자열 의 문 자 는 알파벳 이나 아라비아 숫자 일 수 있 습 니 다.예 를 들 어 AGR 34 나 BEL 4.다음 V 행 에 서 는 각 행 에 2 개의 도시 명 이 있 고 중간 에 빈 칸 으로 나 뉜 다. 예 를 들 어 city 1 city 2 는 city 1 에서 city 2 까지 직통 노선 이 있 고 city 2 에서 city 1 까지 직통 노선 이 있다 고 밝 혔 다.
출력 형식:
첫 번 째 줄 은 여행 코스 에서 방문 한 도시 총수 M 이다.다음 M + 1 줄 은 여행 노선 의 도시 이름 이 고 줄 마다 1 개의 도시 이름 을 쓴다.먼저 도시 명 을 출발 한 다음 에 방문 순서에 따라 다른 도시 명 을 나열 한다.마지막 1 행 (종점 도시) 의 도시 명 은 반드시 출발 도시 명 임 을 주의 하 세 요.문제 가 풀 리 지 않 으 면 'No Solution!' 을 출력 합 니 다.
입 출력 샘플
샘플 입력 \ # 1:

8 9
Vancouver
Yellowknife
Edmonton
Calgary
Winnipeg
Toronto
Montreal
Halifax
Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary

출력 샘플 \ # 1:

7
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver 

설명 하 다.
@ zhouyonglong 이 spj 를 제공 해 주 셔 서 감사합니다.
매 운 닭 제목, 하루 조정, QwQ.
건축 도:
우선, 원 문 제 를 1 에서 n 으로 전환 하여 같은 점 을 거치 지 않 는 가장 긴 경 로 를 찾 습 니 다.
횟수 제한 으로 철거 점 을 생각 하 다.
모든 원 그림 의 변 에 대해 (i + n, j) 의 방향 변 이 있 고 최대 흐름 은 경로 갯 수 입 니 다.
가장 많이 지나 가 는 도시 수 는 달리기 비용 흐름 의 최대 비용 이다.
기록 경로 에 대해 서 는 dfs 에서 검색 할 수 있 습 니 다.
현학 적 퇴 류 조작 이 있 기 때문에 비용 흐름 에 기록 해 서 는 안 된다.
그리고 원 그림 의 변 연 용량 이 inf 인 변 (원인 불명) 이 될 수 없습니다.

#include
#include
#include
#include
#include