도저히 문제자체가 해석이 안되서 여쭈어 봅니다
You are given a directed graph with n vertices. For each vertex, the number of incoming
and outgoing edges is provided. Give a polynomial-time algorithm to find a configuration of
exactly m edges that matches the above setup for the graph, and explain your answer.
일단 이문제를 상황에 맞게 MaxFlow MinCut Bitartite Circulation Circulation with Lower bounds등으로 바꾸는 문제인데 문제자체가 원하는게 잘이해가 안가네요
지금까지 이해한 바로는 그래프가 주어졌을때 위 조건을 만족하는 변들이 총 몇개인지 (m이 얼마인지) 계산하는 알고리즘을 구하라는건가요?
미리 감사드립니다..ㅜㅜ
각각 꼭짓점에 in/out 변의 수가 주어져있다는 부분이요
You are given a directed graph with n vertices. For each vertex, the number of incoming and outgoing edges is provided. Give a polynomial-time algorithm to find a configuration of exactly m edges that matches the above setup for the graph, and explain your answer.
이게 전부입니다 ㅜㅜ
다른 부분은 없이 저게 문제 전부입니다...ㅜ
ㄴㄴ m이 인자로 주어지는거임 m개의 변의로 위의 전제를 만족하는 그래프를 구하는 알고리즘을 찾으라는 갓
감사합니다 혹시 그렇다면 저 문제는 MaxFlow MinCut Bipartite Circulation Circulation with Lower bounds 중 어느것을 이용하는게 맞을지 혹시 아실까요? Circulation with Lower bounds 가 맞는걸까요?
알고리즘 푼지 오래되서 모르겟는걸
네 감사합니다 덕분에 문제를 이해할수있었습니다. 좋은 하루되세요!