[일반] clique 관련 문제 풀어주실분

[익명(223.62)]

무방향, 가중치가 있는 간선을 가지고있는 노드 n개의 완전 연결 그래프에서 m개의 노드를 선택했을때 만들어지는 완전 연결 그래프의 간선 가중치의 최대값 중 최소값을 구하는 방법은?

1<=m<=n<=100

- dc official App

[ㅅㅅ(59.152)]

지금 당장 생각나는 방법은 x이하의 간선들로 m개의 node로 이루어진 완전 연결 그래프를 만들 수 있나? 라는 chk(x) 만들고 이분 탐색

[익명(14.6)]

그렇게했다가 tle받음 - dc App

[ㅅㅅ(59.152)]

ㄷㄷ? 절대 tle 날 수가 없는데.. chk가 o(n^2)에 되고 간선 범위 많아봤자 64번 반복일텐데.. 이분탐색 종료 조건 잘못한거 아님?

[익명(14.6)]

그게대충 조건만족하는 노드들이 너무많을때 문제가 됨 50C16정도에서 터지던걸로 기억 - dc App

[ㅅㅅ(59.152)]

chk 만드는게 좀 까다롭구나.

[ㅅㅅ(59.152)]

걍 아무 생각 없이 O(n^2)이면 될 줄 알았는데 생각 좀 더 해야겠넹

[ㅅㅅ(59.152)]

생각나긴 했는데 정확히 될 지는 모르겠다. 1. 일단 가중치 x이하인 간선들만 남겨두고 그래프 생성 2. 그 그래프에서 현재 deg < m 인 것 삭제 --> 이런 정점이 없어질 때 까지 반복 (만약 삭제된 것으로 인해 deg가 떨어진 것도 고려해야 함) 3. 남은 그래프에서 deg > m 인게 하나라도 있으면 무조건 가능 4. 그런게 없는데 남은 정점이 m개이면 가능, 아님 불가능

[ㅅㅅ(59.152)]

아 예외 있구나.. 나대서 ㅈㅅ

[익명(14.6)]

ㅋㅋㅋ.. 이문제 넘 어랴움 - dc App

[ㅅㅅ(59.152)]

근데 최대 클릭 구하는 다항 시간 알고리즘 있는거 같은데 그걸 쓰면 되지 않을까?

[익명(14.6)]

최대 클릭이라기보단 가중치를 최대로갖는 클릭을 찾는거라 - dc App

[익명(14.6)]

정확히는 최대가중치의 최소를 찾는거지만 - dc App

[ㅅㅅ(59.152)]

ㄴㄴ chk에서는 x이하의 가중치로 이루어진 그래프에서 최대 클릭의 노드 수가 m 이상인지만 판단하면 되지 않음?

[익명(14.6)]

아 이분탐색으로 풀거면 그래도 되긴 하겠네 ㅇㅇ - dc App

[ㅅㅅ(59.152)]

최대 클릭 공부하기 좋은 자료 찾으면 나도 알려줘 ㅜㅜ

[익명(14.6)]

ㅋㅋㅋ그거나도 위키훑다가 접음 넘어려워보여서 ㅋㅋㅋ - dc App