공급자로부터 최대 수신자 수까지의 자원 배포

Question

인터넷이 필요하고 $ m $ < "$ N $ 수학 용기"> $ N $ 수학 용기 "> $ M $ 도시의 인터넷 제공 업체.여기서 도시의 모든 거주자가 인터넷이 필요하며 모든 주민들은 어떤 공급자가 그에게 이용할 수 있는지 알고 있습니다.공식적으로 거주자 $ i $ 공급자 $ a_i $ 의 목록이 있습니다.또한 각 공급자는 그가 제공 할 수있는 최대 연결 수, 즉 공급자 $ i $ 은 최대 $ k_i$ 연결.인터넷을 갖는 주민의 수가 최대가되도록 인터넷을 제공하는 최적의 방법을 찾으십시오.

질문에 대한 나의 생각은이 질문은 역동적 인 프로그래밍을 제안하는 제약 조건에 대한 Knack-Pack 문제의 파생물처럼 보이지만 주를 찾을 수 없습니다.누구도 나를 도울 수 있니?

Answer 1

이 문제는 최대 유량 문제 .

인터넷 공급자 $ p_1, p_2, \ cdots, p_m $ 및 거주자 $ r_1, r_2, \ cdots, r_n $ . 다음과 같이 지정된 흐름 네트워크를 고려하십시오.

• 노드는 $ s, \ p_1, p_2, \ cdots, p_m, \ r_1, r_2, \ cdots, r_n, \ t $ , 여기서 $ S $ 및 $ T $ 은 소스와 싱크에 대해 두 개의 추가 노드가 있습니다.
• $ s $ 및 각 $ p_i $ 사이의 가장자리가 용량 $ k_i $ .
• $ p_i $ 및 $ r_j $ $ P_I $ 은 $ r_j $ 에 인터넷을 제공 할 수 있습니다.
• 각 $ r_j $ 및 $ T $ 사이에 가장자리가 있습니다.

우리가 원하는 것은 $ s $ 에서 $ T $ 에있는 최대 흐름을 찾는 것입니다. < / P>

다항식 시간의 최대 흐름 문제를 해결하기 위해 많은 알고리즘 가 있습니다. 예를 들어, Ford-Fulkerson 알고리즘 및 Dinic의 알고리즘 꽤 인기가 있습니다. 다양한 프로그래밍 언어로 해당 알고리즘을 구현하는 소스 코드를 쉽게 찾을 수 있습니다.

모든 알고리즘은 필수적인 최대 유량을 생성하므로 일부 공급자가 0.42 또는 $ \ fRAC {\ SQRT2} 2를 제공해야한다고 계산 된 최대 유량이 규정 된 경우 걱정하지 않습니다. $ 인터넷을 일부 거주자에게. Integral Flow theorem .

을 확인할 수 있습니다.