글 읽기 - 1939 중량제한 / 이분탐색 + DFS 인데 왜 틀렸을까요?

Green55 6년 전 0

추가로 이분탐색 잘 설명되있는 글 있으면 추천좀 부탁드립니다 항상 햇갈리네요

#include<bits/stdc++.h>
using namespace std;
const int MAX = 100000;
int main(){
	int n,m,s,e,maxC=0;
	vector<pair<int,int>> adj[MAX];
	scanf("%d %d", &n, &m);
	while(m--){
		int a,b,c;
		scanf("%d %d %d", &a, &b, &c);
		adj[a-1].push_back({b-1,c});
		adj[b-1].push_back({a-1,c});
		maxC = max(maxC, c);
	}
	scanf("%d %d", &s, &e);
	s--, e--;
	
	bool visit[MAX]={};
	function<bool(int,int)> DFS = [&](int weight, int here){
		visit[here] = true;
		for(auto &P : adj[here]){
			if(P.second < weight || visit[P.first]) continue;
			DFS(weight, P.first);
		}
		return visit[e];
	};
	int hi = maxC, lo = 0, ans=0;
	while(lo+1 < hi){
		int mid = (hi+lo)/2;
		//printf("%d - %d - %d\n",lo,mid,hi);
		memset(visit,0,sizeof(visit));
		if(DFS(mid,s)) lo = mid +1;
		else hi = mid -1;
	}
	printf("%d", hi);
}

ho94949 6년 전 0

이진탐색의 문제가 맞는것 같네요
제가 주로 쓰는 방법은 다음과 같습니다.:

lo를 답보다 작거나 같다고, hi를 크다고 가정하고, can은 가능한지의 여부입니다.

int lo = 0, hi = 1e9; // l
while(lo+1 != hi)
{
    int mi = (lo+hi)/2;
    if(can(mi)) lo = mi;
    else hi = mi;
}

Green55 6년 전 0

다음과 같이 수정하니 맞았네요.

일단 답이 될 수 있는 maxC가 hi로 설정된 점이 첫번째 문제였습니다.

lo에는 항상 DFS가 참인 값, hi에는 거짓인 값이 저장되게 바꾸고 lo를 출력하니 AC가 떴습니다.

역시 이분탐색은 어려워요..

	int hi = maxC+1, lo = 0, ans=0;
	while(lo+1 < hi){
		int mid = (hi+lo)/2;
		memset(visit,0,sizeof(visit));
		if(DFS(mid,s)) lo = mid;
		else hi = mid;
	}
	printf("%d", lo);

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1939 중량제한 / 이분탐색 + DFS 인데 왜 틀렸을까요?

Green55 6년 전 0

ho94949 6년 전 0

Green55 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말