लिंक में पाया जा सकता hereगणना अव्यवस्थित जोड़े की संख्या समस्या का एक अन-निर्देशित ग्राफ
समस्या वक्तव्य
बर्गर टाउन एक शहर है कि एन विशेष जंक्शनों और एन के होते है -1 मार्ग। जंक्शनों की प्रत्येक जोड़ी के बीच बिल्कुल एक छोटा रास्ता है। जंक्शन मैं (xi, यी) पर स्थित है और के बीच की दूरी दो जंक्शन I, j को टैक्सीकैब ज्यामिति द्वारा परिभाषित किया गया है।
टिम ने हाल ही में टैक्सीकैब ड्राइवर के रूप में काम करने के लिए टैक्सीकैब का भुगतान किया है। उनका वाहन बहुत सस्ता था, लेकिन इसमें बहुत बड़ी कमी है। यह केवल क्षैतिज रूप से H इकाइयों को ड्राइव कर सकता है और ई इकाइयों को ईंधन भरने से पहले लंबवत रूप से ड्राइव कर सकता है।
एक ग्राहक एक दूसरे जंक्शन जे के लिए मैं जंक्शन से लाया जाना चाहता है, तो यह कार इस मार्ग पर मार्ग क्षैतिज दूरी का योग और ऊर्ध्वाधर दूरी का योग ड्राइविंग, iff के ही लायक है क्रमशः एच और वी के बराबर या उसके बराबर।
इसके अलावा, किसी भी दो जंक्शनों के बीच एक अद्वितीय मार्ग है।
अब उसके पास वाहन वापस विक्रेता को वापस करने के बारे में विचार हैं। लेकिन वह पहले जानना चाहता है, अगर यह इसके लायक भी है। यही कारण है कि वह को अनियंत्रित जोड़े (i, j) की संख्या जानने के लिए चाहता है कि यह नहीं है जो कि ग्राहक जंक्शन से जंक्शन जंक्शन तक ड्राइव करने के लिए संभव है।
प्रतिबन्ध
2 ≤ एन ≤ 10^5
0 ≤ एच, वी ≤ 10^14
0 ≤ xi, यी ≤ 10^9
मेरे पास है रिकर्सन के साथ इस समस्या को हल किया। लेकिन कुछ परीक्षण मामलों में, मेरा कोड समय समाप्त हो रहा है।
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
long H = in.nextLong();
long V = in.nextLong();
List<Vertex> vertex = new ArrayList<>();
for (int i=0; i < N; i++) {
Vertex vx = new Vertex(in.nextLong(), in.nextLong());
vertex.add(vx);
}
for (int i=0; i < N-1; i++) {
int fromPath = in.nextInt()-1;
int toPath = in.nextInt()-1;
vertex.get(fromPath).neighbours.add(vertex.get(toPath));
vertex.get(toPath).neighbours.add(vertex.get(fromPath));
}
long count = 0;
for (int i=0; i < N; i++) {
count += (N - findUnorderedPairs(vertex.get(i), null, 0, 0, H, V));
}
System.out.println(count/2);
int temp = 0;
}
private static long findUnorderedPairs(Vertex vertex, Vertex previousVertex, long hor, long vert, long H, long V) {
if (hor > H || vert > V) {
return 0;
}
long result = 1;
for (Vertex v : vertex.neighbours) {
result += (v != previousVertex) ? findUnorderedPairs(v, vertex, hor + Math.abs(vertex.x - v.x), vert + Math.abs(vertex.y - v.y), H, V) : 0;
}
return result;
}
private static class Vertex {
private long x;
private long y;
public ArrayList<Vertex> neighbours;
public Vertex(long x, long y) {
this.x = x;
this.y = y;
neighbours = new ArrayList<>();
}
}
}
मैंने डिजस्ट्रस के कार्यान्वयन के साथ भी प्रयास किया है, लेकिन वहां कोई भाग्य नहीं है।
एक त्वरित समाधान प्राप्त करने के तरीके के बारे में कोई सुझाव वास्तव में सराहना की जाएगी।
क्रस्कल – CodeFox
के एल्गोरिदम का प्रयास करें विवरण विरोधाभासी है। पहले पैराग्राफ में यह कहता है, "जंक्शनों की प्रत्येक जोड़ी के बीच बिल्कुल एक छोटा रास्ता है।" बाद में, यह कहता है, "इसके अलावा, किसी भी दो जंक्शनों के बीच एक अनोखा रास्ता है।" तो यह कौन है? –
@ जिममिशेल मुझे कोई विरोधाभासी नहीं दिख रहा है, 'किसी भी दो जंक्शनों के बीच एक अनोखा मार्ग है' इसका मतलब है कि यह एक जुड़ा हुआ पेड़ है, और यह अद्वितीय मार्ग भी सबसे छोटा रास्ता है। –