스탱님이 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;
질문 있습니다.!!
"v 를 루트로 하는 서브트리에서 간선이 닿는 가장 번호가 작은 점이 u 여야 하고, 이 때 u 와 닿는 점은 반드시 v여야 합니다. "
DFS를 한다면 이미 방문한 노드는 가지 않는거 아닌가요? 부모노드를 생각해주는 이유가 back-edge 때문인가요??@,.@
예 정답입니다. ^^ v 를 루트로 하는 서브트리 전체에서, 자신보다 no[] 가 작은 정점으로 가는 간선이 없어야, (u,v) 를 지울 때 그래프가 끊어지겠죠. v 외의 다른 정점 w 가 있어서 (u,w) 가 있을 경우엔 (u,v) 는 cut edge 가 아닙니다. 따라서 이 경우를 구분하기 위해, (u,v) 를 보지 않을 필요가 있죠. (u,v) 를 제외하고도 v를 루트로 하는 서브트리에서 u 로 가는 간선이 있다면 (u,w) 같은 간선이 있다는 뜻이고, 그러면 cut edge 가 아니니까요.
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) r = solve(there, here);
{
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
if(r.second > no[here]) sol >?= r.first;
totalApples += r.first;
// there 를 루트로 하는 서브트리에서 닿은 노드들도 포함해야겠죠?
minReached <?= r.second;
}
}
return make_pair(totalApples, minReached);
}
[/spoiler]
16년 전