द्वि-दिशा पेड़

Question

फैले मैं interviewstreet.com से इस सवाल में आए

मशीनें एक बार फिर से Xions के राज्य पर हमला किया है। Xions के राज्य में एन शहरों और एन -1 बिडरेक्शनल सड़कों हैं। सड़क नेटवर्क है जैसे कि शहरों की किसी भी जोड़ी के बीच एक अद्वितीय मार्ग है।

मॉर्फियस की खबर है कि के मशीन्स पूरे राज्य को नष्ट करने की योजना बना रहे हैं। ये मशीनें शुरू में के विभिन्न साम्राज्य के शहरों में रह रही हैं और अब से वे हमले की योजना बना सकते हैं और लॉन्च कर सकते हैं। इसलिए उन्होंने को उन सड़कों को नष्ट करने के बाद मशीनों के बीच कनेक्शन को किसी भी दो मशीनों के बीच कोई रास्ता नहीं होना चाहिए, ताकि 0oको बाधित करने के लिए कुछ सड़कों को नष्ट कर दिया जाए।

चूंकि हमले अब से किसी भी समय हो सकता है, इसलिए नियो को यह कार्य जितनी जल्दी हो सके करना है। राज्य में प्रत्येक सड़क को कुछ समय लगता है नष्ट हो जाता है और उन्हें एक समय में केवल एक ही नष्ट किया जा सकता है।

आपको एक प्रोग्राम लिखना होगा जो नियो को न्यूनतम समय बताता है कि उसे मशीनों के बीच कनेक्शन को बाधित करने की आवश्यकता होगी।

नमूना इनपुट इनपुट की पहली पंक्ति में दो, स्पेस से अलग पूर्णांक, एन और के। शहरों को 0 से 0 तक क्रमांकित किया गया है। फिर एन -1 लाइनों का पालन करें, प्रत्येक में तीन, स्पेस से अलग पूर्णांक, एक्स वाई जेड, का अर्थ है कि इस सड़क को नष्ट करने के लिए शहर एक्स और शहर वाई, और को जोड़ने वाली एक द्विपक्षीय सड़क है, जो समय की z इकाइयां लेती है। फिर के लाइनों प्रत्येक का एक पूर्णांक युक्त का पालन करें। आईथ पूर्णांक शहर की आईडी है जिसमें ith मशीन वर्तमान में स्थित है।

आउटपुट प्रारूप एक ही पंक्ति में प्रिंट करें के लिए आवश्यक न्यूनतम समय मशीनों के बीच कनेक्शन को बाधित करता है।

नमूना इनपुट

5 3 
2 1 8 
1 0 5 
2 4 5 
1 3 4 
2 
4 
0 

नमूना आउटपुट

10 

स्पष्टीकरण नव सड़क शहर 2 और वजन 5 के शहर 4 जोड़ने नष्ट कर सकते हैं, और सड़क शहर 0 जोड़ने और वजन 1 का शहर 1। एक समय में केवल एक सड़क को नष्ट किया जा सकता है, कुल न्यूनतम समयलिया गयासमय की 10 इकाइयां हैं। इन सड़कों को नष्ट करने के बाद मशीनों में से कोई भी किसी भी पथ के माध्यम से अन्य मशीन तक पहुंच सकता है।

प्रतिबन्ध

2 <= N <= 100,000 
2 <= K <= N 
1 <= time to destroy a road <= 1000,000 

कोई कैसे समाधान दृष्टिकोण विचार दे सकते हैं।

Answer 1

तीनों उत्तर सही समाधान के लिए नेतृत्व करेंगे, लेकिन आप interviewstreet.com द्वारा प्रदान की समय सीमा के भीतर समाधान हासिल नहीं कर सकते। इस समस्या को सफलतापूर्वक हल करने के लिए आपको कुछ सरल दृष्टिकोण के बारे में सोचना होगा।

संकेत: नोड जहां मशीन मौजूद है से शुरू करते हैं।

Answer 2

राज्य एन शहरों, एन -1 किनारों है और यह पूरी तरह से जुड़ा हुआ है, इसलिए हमारे राज्य (ग्राफ सिद्धांत में) tree है। इस तस्वीर पर आप अपने इनपुट ग्राफ़ के पेड़ का प्रतिनिधित्व देख सकते हैं जिसमें मशीनों को लाल शिखर से दर्शाया जाता है।

जिस तरह से आपको रूट चरम से सभी पथों को सभी पत्ते नोड्स पर विचार करना चाहिए। तो हर रास्ते में आपके पास कई लाल नोड्स होंगे और किनारों को हटाने के दौरान आपको केवल पड़ोसी लाल नोड्स को ध्यान में रखना चाहिए। उदाहरण के लिए पथ 0-10 में दो अर्थपूर्ण जोड़े हैं - (0,3) और (3,10)। और आपको जोड़ों में जुड़े हुए कोने वाले प्रत्येक पथ से बिल्कुल एक नोड (कम नहीं, अधिक नहीं) को हटा देना होगा।

मुझे आशा है कि यह सलाह सहायक होगी।

Answer 3

जैसा कि दूसरों ने कहा है, एन वर्टिस और एन -1 किनारों वाला एक कनेक्टेड ग्राफ एक पेड़ है।

इस तरह की समस्या लालची समाधान के लिए पूछती है; मैं Kruskal's algorithm:

प्रत्येक नोड (शहर) के लिए एन घटकों के एक सेट के साथ शुरू करें। ट्रैक रखें कि कौन से घटकों में मशीन पर कब्जा कर लिया गया शहर है।

एक समय में 1 किनारे (सड़क) लें, वजन घटाने के क्रम (क्रमशः नष्ट करने के लिए सबसे महंगी सड़कों से शुरू)। - इस बढ़त के लिए (जो जरूरी दो घटकों को जोड़ता ग्राफ एक पेड़ है):

• अगर दोनों neigboring घटकों एक मशीन के कब्जे वाले शहर के होते हैं, इस सड़क नष्ट किया जाना चाहिए, अन्यथा रूप में इस तरह
• में चिह्नित, विलय एक में neigboring घटक। अगर उनमें से एक मशीन पर कब्जा कर लिया गया शहर है, तो विलय घटक भी है।

आप सभी किनारों के साथ काम हो गया है, को नष्ट कर दिया सड़कों के लिए लागत की राशि वापस जाएँ।

जटिलता क्रुस्कल के एल्गोरिदम के समान ही होगी, जो कि अच्छी तरह से चुने गए डेटा संरचना और सॉर्टिंग विधि के लिए लगभग रैखिक है।

Answer 4

Pjotr ​​एक सही जवाब है (हालांकि काफी asymptotically इष्टतम नहीं), लेकिन इस बयान है

समस्या इस तरह की एक लालची समाधान के लिए पूछता है

वास्तव में असली दुनिया में के रूप में, सबूत की आवश्यकता है (प्रतिस्पर्धी प्रोग्रामिंग से प्रतिष्ठित), इस “ दयालु ” की कई समस्याएं हैं जिनके लिए लालची समाधान इष्टतम नहीं है (उदाहरण के लिए, सामान्य ग्राफ में यह वही समस्या है, जिसे बहुआयामी कट कहा जाता है डी एनपी-हार्ड है)। इस मामले में, सबूत matroid सिद्धांतों को सत्यापित करने के होते हैं। किनारों का एक सेट ए और subseteq; ई स्वतंत्र यदि ग्राफ (वी, ई और सेटमिनस; ए) बिल्कुल है | ए | कम से कम एक मशीन युक्त + 1 जुड़े घटक।

खाली सेट की स्वतंत्रता। ट्रिविअल।

वंशानुगत संपत्ति। एक स्वतंत्र सेट बनने दें। प्रत्येक किनारे ई ∈ ए ग्राफ के दो जुड़े घटकों (वी, ई और सेटमिनस; ए) में शामिल हो जाता है, और प्रत्येक जुड़े घटक में कम से कम एक मशीन होती है। ग्राफ में ई वापस डालने में, कम से कम एक मशीन युक्त कनेक्टेड घटकों की संख्या 1 से कम हो जाती है, इसलिए ए और सेटमिनस; {ई} भी स्वतंत्र है।

विस्तार संपत्ति। ए और बी को स्वतंत्र सेट के साथ | ए | < | बी | चूंकि (वी, ई और सेटमिनस; बी) से अधिक जुड़े घटक हैं (वी, ई और सेटमिनस; ए), कबूतर सिद्धांत द्वारा मौजूद मशीनों की एक जोड़ी है, v जैसे कि आप और वी बी द्वारा डिस्कनेक्ट हैं लेकिन ए द्वारा नहीं। चूंकि यू से वी तक बिल्कुल एक रास्ता है, बी में इस पथ पर कम से कम एक किनारे ई है, और ए में ई नहीं हो सकता है। ए ∪ {e} को हटाने से एक से अधिक कनेक्टेड घटक शामिल होते हैं जिसमें ए से कम से कम एक मशीन होती है, इसलिए ∪ {e} आवश्यकतानुसार स्वतंत्र है।

Answer 5

मैं कुछ कोड लिखता हूं, और सभी परीक्षणों को चिपकाता हूं।

#include <iostream> 
#include<algorithm> 
using namespace std; 

class Line { 
public: 
    Line(){ 
     begin=0;end=0; weight=0; 
} 
int begin;int end;int weight; 

bool operator<(const Line& _l)const { 
    return weight>_l.weight; 
} 
}; 

class Point{ 
public: 
Point(){ 
    pre=0;machine=false; 
} 
int pre; 
bool machine; 
}; 

void DP_Matrix(); 
void outputLines(Line* lines,Point* points,int N); 

int main() { 
    DP_Matrix(); 
    system("pause"); 
    return 0; 
} 

int FMSFind(Point* trees,int x){ 
    int r=x; 
    while(trees[r].pre!=r) 
     r=trees[r].pre; 
    int i=x;int j; 
    while(i!=r) { 
      j=trees[i].pre; 
     trees[i].pre=r; 
     i=j; 
    } 
return r; 
} 

void DP_Matrix(){ 
int N,K,machine_index;scanf("%d%d",&N,&K); 
Line* lines=new Line[100000]; 
Point* points=new Point[100000]; 
N--; 
for(int i=0;i<N;i++) { 
    scanf("%d%d%d",&lines[i].begin,&lines[i].end,&lines[i].weight); 
    points[i].pre=i; 
} 
points[N].pre=N; 
for(int i=0;i<K;i++) { 
    scanf("%d",&machine_index); 
    points[machine_index].machine=true; 
} 
long long finalRes=0; 
for(int i=0;i<N;i++) { 
    int bP=FMSFind(points,lines[i].begin); 
    int eP=FMSFind(points,lines[i].end); 
    if(points[bP].machine&&points[eP].machine){ 
     finalRes+=lines[i].weight; 
    } 
    else{ 
     points[bP].pre=eP; 
     points[eP].machine=points[bP].machine||points[eP].machine; 
     points[bP].machine=points[eP].machine; 
    } 
} 
cout<<finalRes<<endl; 
delete[] lines; 
delete[] points; 
} 

void outputLines(Line* lines,Point* points,int N){ 
printf("\nLines:\n"); 
for(int i=0;i<N;i++){ 
    printf("%d\t%d\t%d\n",lines[i].begin,lines[i].end,lines[i].weight); 
} 
printf("\nPoints:\n"); 
for(int i=0;i<=N;i++){ 
    printf("%d\t%d\t%d\n",i,points[i].machine,points[i].pre); 
} 
} 

Answer 6

किसी भी मशीन नोड्स से डीएफएस निष्पादित करना प्रारंभ करें। इसके अलावा, अब तक का सामना करने वाले न्यूनतम वजन के साथ किनारे का ट्रैक रखें। जैसे ही आपको अगली नोड मिलती है जिसमें मशीन भी होती है, अब तक दर्ज किए गए न्यूनतम किनारे को हटा दें। इस नए नोड से अब डीएफएस शुरू करें। तब तक दोहराएं जब तक कि आपको सभी नोड्स नहीं मिलते हैं जहां मशीन मौजूद है।

हे (एन) कि जिस तरह से ऐसा होना चाहिए !!