1. 문제
https://www.acmicpc.net/problem/1939
1939: 무게 제한
N 및 M(1 ≤ M ≤ 100,000)은 첫 번째 줄에 지정됩니다. 다음 M 행에는 브리지에 대한 정보를 나타내는 세 개의 정수 A, B(1 ≤ A, B ≤ N) 및 C(1 ≤ C ≤ 1,000,000,000)가 제공됩니다. 이것은 A 섬과 B 섬 사이에 무게 제한이 없음을 의미합니다.
www.acmicpc.net
2. 솔루션 포인트
- 두 부분으로 구성된 검색 + BFS로 해결
- 주요 데이터 구조
- 목록
() inList : 인접 리스트 - long min : 주어진 간선 중 최소값
- long max : 주어진 edge의 최대값
- boolean() Visited : 방문 체크 배열
- 목록
- 각 다리에 무게가 할당되고 그 무게를 초과하지 않고 공장에서 공장으로 이동할 수 있는 최대 무게를 찾습니다.
- 이 문제는 이진 검색에 관한 것입니다. 트렁크 비용오전.
- 핵심은 이진 검색으로 Edge의 가중치를 결정한 후 BFS를 실행할 때 시작 노드(이 문제의 첫 번째 공장)에서 끝 노드(두 번째 공장)로 이동할 수 있는 최대 가중치를 찾는 것입니다.
3. 논리 풀기
- 입력이 주어지면 양방향 인접 목록을 생성합니다.
- 들어갈 때 부족 최소값 최대값컴퓨터에 저장
- 이것은 두 부분으로 구성된 검색에서 나중에 수행됩니다. 왼쪽, 오른쪽으로 사용가치
- 두 부분으로 구성된 검색 기능 weightRestrictionBinarySearch()달리다
- 가장자리의 최대값과 최소값 왼쪽, 오른쪽으로 두 부분으로 구성된 검색의 양쪽 끝에서 값을 설정하도록 설정합니다.
- 왼쪽 <= 오른쪽으로 평균은 (왼쪽 + 오른쪽) / 2에서 .
- 이거는 WeightConstraintBFS()BFS를 실행합니다.
- BFS 기능을 수행할 때 queue에서 가져온 객체가 터미널 노드라면 i. 시간. 두 번째 공장 진실두 번째 공장으로 이동할 수 없는 경우 반환 잘못된보고
- 이 시점에서 다음 노드를 찾을 때 주의해야 합니다. “센터가다 다음 노드 에지의 가중치가 작거나 같으면 검색할 수 있습니다.”
- 다리를 건너려면 그 가장자리의 무게보다 작거나 같아야 하기 때문입니다.
- 만약에 WeightConstraintBFS()반환된 값 진실이것은 평균 집합으로 목표가 달성되었음을 의미하므로 결과를 업데이트하고 왼쪽 값을 평균 + 1로 설정합니다.
- 만약에 반환된 값 잘못된, 목표가 충족되지 않았으므로 값을 줄여야 함을 의미합니다. 따라서 오른쪽에 중앙 – 1의 값을 할당합니다.
4. 소스 코드
import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N; // 섬의 개수
static int M; // 다리의 개수
static class Node {
int v;
long cost;
public Node(int v, long cost) {
this.v = v;
this.cost = cost;
}
}
static List<Node>() inList; // 인접 리스트
static long result = Integer.MIN_VALUE;
static int start, end;
static long min = Integer.MAX_VALUE; // 주어진 간선 중 최솟값
static long max = Integer.MIN_VALUE; // 주어진 간선 중 최대 값
static boolean() visited;
public static void main(String() args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 입력을 받아 변수 초기화 및 인접리스트 초기화
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
inList = new ArrayList(N + 1);
for (int i = 1; i <= N; i++) {
inList(i) = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
inList(from).add(new Node(to, cost));
inList(to).add(new Node(from, cost));
// 간선의 최대값 구하기
min = Long.min(min, cost);
max = Long.max(max, cost);
}
// 출발 노드 번호 및 도착 노드 번호
st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
end = Integer.parseInt(st.nextToken());
// 이분탐색 함수 시작
weightRestrictionBinarySearch();
//결과 출력
bw.write(Long.toString(result));
bw.flush();
bw.close();
br.close();
}
// 이분 탐색 함수 : 이분탐색의 주체는 간선의 비용
private static void weightRestrictionBinarySearch() {
long left = min;
long right = max;
// weightRestrictionBFS의 리턴 값은 true or false
// 만약 true가 리턴 됬다는 것은 도착지점에 도착했다는 것이므로 result를 갱신
while (left <= right) {
long mid = (left + right) / 2;
if (weightRestrictionBFS(mid)) {
result = Long.max(result, mid);
left = mid + 1;
} else {
right = mid - 1;
}
}
}
// bfs 함수
private static boolean weightRestrictionBFS(long mid) {
// 방문 배열
visited = new boolean(N + 1);
// BFS를 위한 큐
Queue<Node> q = new ArrayDeque<>();
q.add(new Node(start, mid));
visited(start) = true;
while (!q.isEmpty()) {
Node poll = q.poll();
// 두번째 공장에 도착했다면
if (poll.v == end) {
return true;
}
for (int i = 0; i < inList(poll.v).size(); i++) {
// 연결된 노드가 null이 아니고, 방문 처리하지 않았고,
// 지금 탐색하는 cost가 다음 노드 간선의 cost보다 작거나 같을 때 탐색할 수 있음
if (inList(poll.v).get(i) != null && !visited(inList(poll.v).get(i).v)
&& mid <= inList(poll.v).get(i).cost) {
visited(inList(poll.v).get(i).v) = true;
q.add(new Node(inList(poll.v).get(i).v, mid));
}
}
}
return false;
}
}
5. 결과
65/100