एन और मशरूम
यदि ग्राफ़ में चक्र हैं (कोई टोपोलॉजिकल सॉर्ट नहीं है), तो दो तरकीबें मदद कर सकती हैं:
1) डायनामिक्स n बार परिकलित करें, जहाँ n ग्राफ़ में शीर्षों की संख्या है (Ford-Bellman एल्गोरिथम के अनुरूप)। लेकिन यह स्पर्शोन्मुखता को बढ़ाता है और सामान्य रूप से शायद ही कभी कुशल होता है।
2) ग्राफ संक्षेपण का निर्माण करें। मूल ग्राफ के प्रत्येक दृढ़ता से जुड़े घटक के लिए, समस्या को अलग से हल करें। संघनित ग्राफ विश्वकोश है और इसके लिए आप टोपोलॉजिकल सॉर्टिंग के साथ मानक दृष्टिकोण का उपयोग कर सकते हैं, जबकि शीर्ष मूल्यों के रूप में उपयोग करते हुए, दृढ़ता से जुड़े घटकों के लिए परिकलित मान। मुख्य रूप से इस पद्धति का प्रयोग किया जाता है।
Problem
एन मशरूम इकट्ठा करने के लिए अपने मशरूम वन जाती है।
मशरूम फ़ॉरेस्ट में n पेड़ों को जोड़ने वाले उन्मुख रास्ते हैं। हर रास्ते पर मशरूम उगते हैं। जब एन एक रास्ते पर चलता है, तो वह उस रास्ते के सभी मशरूम उठा लेता है। हालाँकि, मशरूम फ़ॉरेस्ट में इतनी उपजाऊ मिट्टी होती है कि मशरूम शानदार दर से बढ़ते हैं। जैसे ही एन रास्ते में मशरूम चुनना समाप्त करता है, नए मशरूम उग आते हैं। अर्थात्, एन के बाद i-वें समय के लिए पथ के साथ गुजरता है, मैं इस मार्ग से पहले की तुलना में कम मशरूम उगता हूं। इस प्रकार, यदि पथ में शुरू में x मशरूम थे, तो En पहले पास में x मशरूम, दूसरे में x - 1 मशरूम, तीसरे में x - - - 2 मशरूम इकट्ठा करेगा, और इसी तरह पर। हालांकि, मशरूम की संख्या 0 से कम नहीं हो सकती।
उदाहरण के लिए, शुरुआत में रास्ते में 9 मशरूम उगने दें। फिर एक से चार पास करने के लिए एन द्वारा एकत्र किए जाने वाले मशरूम की संख्या 9, 8, 6 और 3 है। पाँचवीं पास के बाद से, एन इस रास्ते से कुछ भी इकट्ठा नहीं कर पाएगा (लेकिन फिर भी उस पर चल सकता है)।
एन पेड़ एस से शुरू करने का फैसला किया। केवल बताए गए रास्तों पर चलकर वह अधिकतम कितने मशरूम एकत्र कर सकता है?
इनपुट:
पहली पंक्ति में दो पूर्णांक n और m (1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) — मशरूम फ़ॉरेस्ट में क्रमशः पेड़ों की संख्या और उन्मुख पथों की संख्या।
अगली m पंक्तियों में से प्रत्येक में तीन पूर्णांक x, y और w हैं (1 ≤ x, y ≤ n, 0 ≤ w ≤ 108 ) एक ऐसे रास्ते का वर्णन करता है जो शुरू में w मशरूम के साथ पेड़ x से पेड़ y तक जाता है। ऐसे रास्ते हैं जो एक पेड़ से एक ही पेड़ तक जाते हैं, साथ ही कई रास्ते पेड़ों के एक ही जोड़े को जोड़ते हैं।
अंतिम पंक्ति में एक पूर्णांक s (1 ≤ s ≤ n) — एन की प्रारंभिक स्थिति।
आउटपुट:
एक पूर्णांक प्रिंट करें — एन अपने रास्ते में अधिकतम कितने मशरूम इकट्ठा कर सकती है।
उदाहरण:
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;">
<शरीर>
| इनपुट |
आउटपुट |
2 2
1 2 4
2 1 4
1 |
16 |
3 3
1 2 4
2 3 3
1 3 8
1 |
8 |
स्पष्टीकरण:
पहले उदाहरण में, एन सर्कल के चारों ओर तीन बार जा सकता है और 4 + 4 + 3 + 3 + 1 + 1 = 16 मशरूम इकट्ठा कर सकता है। उसके बाद, एन के लिए कोई मशरूम नहीं बचेगा।
दूसरे उदाहरण में एन पेड़ 3 पर जा सकता है और पेड़ 1 से पेड़ 3 तक के रास्ते में 8 मशरूम चुन सकता है।