फोर्ड फुल्कर्सन का उपयोग करके द्विपक्षीय ग्राफ में अधिकतम प्रवाह

Question

के लिए मूल्य निर्धारित करने के लिए मूल्य निर्धारित करने के लिए मैं इस स्थिति में फोर्ड फुलकर्सन एल्गोरिदम का उपयोग कैसे करना चाहिए, यह स्थिति थोड़ी सुडोकू जैसी है। हमारे पास एक मैट्रिक्स a है जिसमें पूर्णांक मान हैं। प्रत्येक पंक्ति का अंतिम स्तंभ और प्रत्येक कॉलम की अंतिम पंक्ति में, संपूर्ण पंक्ति/कॉलम का योग होता है।

उदाहरण:

int[][] a = {{1, 3, 5, 9}, 
      {4, 2, 1, 7}, 
      {5, 5, 6, *}} // * Is not determined since the sums 
          // * do not count as summable values. 

यह बात यह है कि मैट्रिक्स के भीतर मूल्यों हमेशा सही नहीं हैं। राशि के लिए मूल्यों को हमेशा सही, उदाहरण के लिए कर रहे हैं:

int[][] a = {{1, 3, 3, 9}, 
      {2, 3, 1, 7}, 
      {5, 5, 6, *}} // * Is not determined since the sums do 
          // * not count as summable values. 

एक मैट्रिक्स b जो अधिकतम अंतर एक सेल दी राशि को पूरा करने में हो सकता है शामिल नहीं है। उदाहरण के लिए

int[][] b = {{1, 0, 3}, 
      {2, 1, 2}} 

a[0][0] का मूल्य है, जो 1, अधिकतम मतभेद है के लिए उदाहरण के लिए b[0][0] में मूल्य है, जो 1 है है, इसलिए a[0][0] पर मूल्य और सभी के लिए 0 या 2 अधिकतम बदला जा सकता है (बीच की संख्या, लेकिन इस उदाहरण के लिए हमारे पास केवल 2 विकल्प हैं)।

मेरे सवाल यह है: एक मैट्रिक्स a और अधिकतम मतभेद आवश्यक राशि को पूरा करने के लिए किया जा सकता है जिसके साथ एक मैट्रिक्स b (अवैध किसी दिए गए राशि के लिए मूल्यों के साथ), मैं कैसे निर्धारित कर सकते हैं मौसम यह दिया साथ भी संभव है को देखते हुए अधिकतम अंतर और मैं इस तरह के मैट्रिक्स का वैध परिणाम कैसे प्राप्त करूं (यदि ऐसा है तो)।

मेरे वर्तमान दृष्टिकोण (जो नहीं काम करता है):

• पंक्तियों और स्तंभों की एक द्विपक्षीय ग्राफ करें, ताकि आप एक स्रोत, एक सिंक और प्रत्येक पंक्ति और स्तंभ के लिए एक नोड है।
• फिर प्रत्येक पंक्ति को प्रत्येक पंक्ति से कनेक्ट करें।
• फिर स्रोत को प्रत्येक पंक्ति से कनेक्ट करें।
• फिर प्रत्येक कॉलम को सिंक से कनेक्ट करें।
• स्रोत से किनारों के लिए प्रत्येक पंक्ति-नोड को गणित के लिए सेट सेट करें। एब्स (a में संख्याओं की वर्तमान योग - a (उस पंक्ति के लिए) में संख्याओं का योग दिया गया है)।
• प्रत्येक स्तंभ-नोड से किनारों के किनारों के लिए समान है (लेकिन कॉलम के लिए इस बार रकम के लिए)।
• प्रत्येक सेल के अनुसार b में दिए गए अधिकतम अंतरों के लिए पंक्तियों के लिए पंक्तियों के लिए नोड्स के बीच क्षमताओं को सेट करें।
• अधिकतम प्रवाह निर्धारित करने के लिए फोर्ड फुलकर्सन का उपयोग करें।

मैं नहीं जानता कि मैं कैसे एल्गोरिथ्म के अपने परिणामों का उपयोग करना चाहिए मैट्रिक्स a के लिए सही मान निर्धारित करने के लिए प्रत्येक पंक्ति और स्तंभ के लिए दिए गए राशि को पूरा करने के।

Answer 1

तो मैं इस समस्या को अपने आप का हल मिल गया: - प्रत्येक I के लिए B, j

आप मूल्यों मैट्रिक्स A[i][j] और मतभेदों मैट्रिक्स B[i][j] है, तो आप A घटाना करने के लिए होगा। फिर आपको पंक्तियों का उपयोग बाएं नोड्स और कॉलम को सही नोड्स के रूप में उपयोग करके एक द्विपक्षीय ग्राफ बनाना होगा।

आपको फिर प्रत्येक पंक्ति नोड्स को कॉलम नोड्स और इसके विपरीत कनेक्ट करना होगा। स्रोत को सभी पंक्ति नोड्स से कनेक्ट करें और सभी कॉलम नोड्स को सिंक से कनेक्ट करें।

स्रोत से पंक्ति नोड के प्रत्येक किनारे की क्षमता संख्याओं की वर्तमान योग है और कॉलम नोड्स की किनारों की कैपेटियों के लिए भी यही है।

पंक्ति-नोड और कॉलम-नोड के बीच प्रत्येक क्षमता वर्तमान B[i][j] * 2. है तो आपके पास एक पूरा नेटवर्क होना चाहिए।

एडमंड्स कार्प के साथ फोर्ड फुलकर्सन का उपयोग करें। प्रत्येक पंक्ति-नोड और कॉलम-नोड के बीच का प्रवाह वह संख्या है जिसे वर्तमान A[i][j] में जोड़ा जाना चाहिए।

आपके परिणामस्वरूप A मैट्रिक्स आपका उत्तर होगा।