엄청나게 큰수를 설정해놓고
그래프를 입력받을 때
가중치=큰수-원래입력받은가중치
를 넣어주고
다익스트라돌리고 역추척하면 되려나
그래프를 입력받을 때
가중치=큰수-원래입력받은가중치
를 넣어주고
다익스트라돌리고 역추척하면 되려나
[일반] 그래프 최대가중치 경로찾을때 이런거 되지?
익명(106.101)
2022-12-26 10:55
추천 0
댓글 5
다른 게시글
-
ㅅㅂ 평범한 배낭이랑 최단거리 일주일동안 붙잡고있었는데 ㅋㅋ [3][일반] 익명(211.36) | 22.12.26추천 0
-
파이썬으로 코테 준비하려면 어떤 책or강의가 좋음?? [3][일반] 익명(118.235) | 22.12.26추천 0
-
AGC D이후는 도대체 어떻게 푸는거냐 [4][일반] 대학원오지..(publfl) | 22.12.26추천 1
-
tlwpdus 종료 직전 버저비터로 agc 10등 ㄷㄷ [1][일반] 익명(106.101) | 22.12.26추천 0
-
질문 [2][일반] 익명(121.144) | 22.12.25추천 0
-
깃허브 꾸미기 개귀찮다 ㄹㅇ[일반] 익명(221.159) | 22.12.25추천 0
-
아 인생 허비했다 [1][팁] 익명(118.235) | 22.12.25추천 0
-
내년 목표 [1][일반] 익명(223.63) | 22.12.25추천 0
-
코테 이제 막 시작했는데 [2][일반] 익명(180.230) | 22.12.25추천 0
-
굿바이boj 핸들 수정은 못하겟지 [1][일반] 익명(124.49) | 22.12.25추천 0
최대가중치 경로는 NP일텐데요 (해밀턴경로가 NP임)
DAG면 가능하긴 한데 일반적인 그래프에서는 NP-Hard라고 합니다
고마워요~
MST면 가능한데 다익은 사용하는 간선수가 일정하지 않아서 안 됨
최대 스패닝 트리라면 가능은 하겠다만