[editorial] 9월 20일 모의고사 에디토리얼 (A번)

  • JongMan
    JongMan

    스탱님이 best submission 으로 네문제나 선정해 주셔서 그저 황공한 JM 입니다. 굽신굽신
    그나저나 오픈렉쳐 게시판 1등이다 ㅎㅅㅎ
    A - Apple Tree [문제링크]
    역시 중국대회답게 문법도 조금씩 틀렸고 읽기 힘든데 잘 읽어보면 다음과 같은 뜻입니다:
    그래프에서 간선 하나를 잘랐을 때, 1번 정점과 연결되지 않게 되는 정점들을 내가 먹게 된다. 이 정점들의 가중치의 합을 최대화하자.
    에.. 그러니까 일단 잘랐을 때 그래프가 두 개 이상으로 쪼개지는 간선들을 찾는다고 생각하면 쉽죠.
    관련된 문제로 그래프의 절단점(cut vertex, 위키피디아 링크) 찾기 문제가 있죠. 여기 뒤에 보면 depth-first search 를 이용해서 O(m+n) 시간에 찾을 수 있다고 하는데 이걸 쓰면 됩니다. 이거이 Tarjan 이라는 아저씨가 만든 알고리즘인데 여기가면 설명 잘되어 있습니다. [링크] 뭐 이해하기 힘드실 수도 있지만 이걸 여기서 설명하는건 너무 기니 다음 기회에 ^^
    일단 이걸 이해하시면, 이걸 변형해서 그래프의 cut edge (그래프를 두개로 쪼개는 간선) 를 찾는 것이 가능합니다. cut edge 의 양쪽 두 점은 모두 cut vertex 가 되니까요.
    DFS 스패닝 트리에서, 현재 점 u 가 자손 v 를 탐색했습니다. 이 때 (u, v) 가 cut edge 이려면, v 를 루트로 하는 서브트리에서 간선이 닿는 가장 번호가 작은 점이 u 여야 하고, 이 때 u 와 닿는 점은 반드시 v여야 합니다. 따라서, v를 루트로 하는 서브트리를 탐색할 때 v의 부모로 가는 간선을 무시하도록 하면, 이 서브트리에서 닿을 수 있는 가장 번호가 작은 정점은 u의 번호보다 커야겠죠? 따라서 DFS 스패닝 트리 상에 현재 노드의 부모의 번호를 재귀호출시에 추가로 지정해서 이 간선을 무시하도록 하고, 이 간선 빼고는 u 에 닿는 간선도 없다고 하면 (u,v) 가 cut edge 인 것을 알 수 있겠지요.
    이 때 (u,v) 를 자름으로써 먹을 수 있는 사과들의 가치는 v를 루트로 하는 서브트리들의 가중치의 합입니다. 이거를 추가한 DFS 함수가 아래 있습니다. solve() 는 (서브트리 노드 가중치의 합, 서브트리에서 엣지가 닿은 노드 중 가장 번호가 작은 노드의 번호) 의 쌍을 리턴합니다.

    [spoiler="더 보기..."]pair solve(int here, int parent = -1)
    {
    no[here] = timestamp++;
    int totalApples = taste[here];
    // here 를 루트로 하는 서브트리에서 간선이 닿는 노드 중 가장 작은 번호
    int minReached = no[here];
    REP(i,adj[here].sz)
    {
    int there = adj[here][i];
    if(there == parent) continue;
    // 이미 방문한 노드면 minReached 만 업데이트
    if(no[there] != -1)
    minReached <?= no[there];
    else
    {
    pair r = solve(there, here);
    if(r.second > no[here]) sol >?= r.first;
    totalApples += r.first;
    // there 를 루트로 하는 서브트리에서 닿은 노드들도 포함해야겠죠?
    minReached <?= r.second;

    }
    }
    return make_pair(totalApples, minReached);
    }

    [/spoiler]

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]


    12년 전
3개의 댓글이 있습니다.
  • JongMan
    JongMan

    잘못 쓴거 입큰이 정정해줘서 고쳤습니다. 입큰 만세!


    12년 전 link
  • @,.@
    @,.@

    질문 있습니다.!!
    "v 를 루트로 하는 서브트리에서 간선이 닿는 가장 번호가 작은 점이 u 여야 하고, 이 때 u 와 닿는 점은 반드시 v여야 합니다. "
    DFS를 한다면 이미 방문한 노드는 가지 않는거 아닌가요? 부모노드를 생각해주는 이유가 back-edge 때문인가요??@,.@


    12년 전 link
  • JongMan
    JongMan

    예 정답입니다. ^^ v 를 루트로 하는 서브트리 전체에서, 자신보다 no[] 가 작은 정점으로 가는 간선이 없어야, (u,v) 를 지울 때 그래프가 끊어지겠죠. v 외의 다른 정점 w 가 있어서 (u,w) 가 있을 경우엔 (u,v) 는 cut edge 가 아닙니다. 따라서 이 경우를 구분하기 위해, (u,v) 를 보지 않을 필요가 있죠. (u,v) 를 제외하고도 v를 루트로 하는 서브트리에서 u 로 가는 간선이 있다면 (u,w) 같은 간선이 있다는 뜻이고, 그러면 cut edge 가 아니니까요.


    12년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.