Для данного дерева назначьте веса каждому ребру, чтобы минимизировать вес каждого пути (u, v) в дереве.

Question

Для данного дерева присвойте веса каждому ребру, чтобы минимизировать вес каждого пути (u, v) в дереве. Чтобы уточнить, мы минимизируем максимальный вес на каждом пути в дереве

Можно ли решить этот вопрос с помощью какой-либо структуры данных или алгоритма? Как вы определяете, какие веса разместить на каждом ребре дерева? Входные данные - это число N, и вы должны поместить веса между значениями [0, N-2] (включительно) на каждом ребре дерева.

Позвольте мне уточнить вопрос. Допустим, у вас есть ребро (1, 2), и вы кладете вес 3 на это ребро. Фактическое определение «веса» в контексте вопроса - это минимальное значение из [0, N-2], которое НЕ присутствует на пути от (u, v). Несмотря на то, что вес на указанном ребре c равен трем, фактический вес в контексте вопроса равен нулю. Кроме того, root дерева в этом вопросе равно 1.

Мой оригинальный подход к этому вопросу заключался в добавлении значений из [0, N-2] (значения ребер, которые мы можем назначить каждому ребру ) в стек, затем переберите дерево с помощью DFS, извлеките значение из стека (максимальное значение ребра) и назначьте его ребру. Это, однако, не минимизирует стоимость по всем путям. Имейте в виду, что стоимость - это минимальное значение, отсутствующее на пути к (u, v). Мы стараемся минимизировать затраты на каждом возможном пути.

Мой код:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Stack;
import java.util.Iterator;
import java.util.ArrayList;
    public class Mex    {
        public static void main (String [] args) throws IOException {
            BufferedReader b1 = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(b1.readLine());
            LinkedList<Integer>[] adj = new LinkedList[n+1];
            ArrayList<Integer> v = new ArrayList<Integer>(n+1);
            for(int i = 1; i<=n; i++) {
                adj[i] = new LinkedList<Integer>();
            }
            for(int i = 0; i<n-1; i++) {
                String [] edge = (b1.readLine()).split(" ");
                adj[Integer.parseInt(edge[0])].add(Integer.parseInt(edge[1]));
                adj[Integer.parseInt(edge[1])].add(Integer.parseInt(edge[0]));
                v.add(Integer.parseInt(edge[0]));
                v.add(Integer.parseInt(edge[1]));
            }
            dfs(adj, 1, n, v);


        }
        static void dfs(LinkedList<Integer> adj[], int u, int n, ArrayList<Integer> order)   { 
            Stack<Integer> values = new Stack<>();
            int [][] weight = new int[n+1][n+1];
            for(int i = 0; i<n-1; i++) {
                values.push(i);
            }
            boolean [] visited = new boolean[n+1];
            int [] parent = new int[n+1];
            for (int i = 1; i < n+1; i++) 
                visited[i] = false; 

            Stack<Integer> stack = new Stack<>(); 

            stack.push(u); 

            while(stack.empty() == false) { 
                u = stack.peek(); 
                stack.pop(); 

                if(visited[u] == false)  { 
                  visited[u]  = true; 
                  if(u!= 1) {
                    if(adj[u].size()==1) {
                        if(values.contains(0)) {
                            weight[parent[u]][u] = 0;
                            values.remove(0);
                        }
                        else {
                            int w = values.pop();
                            weight[parent[u]][u] = w;
                        }
                    }
                    else {
                        int w = values.pop();
                        weight[parent[u]][u] = w;   
                    }
                  }
                } 

                Iterator<Integer> itr = adj[u].iterator(); 

                while (itr.hasNext())  {                    
                    int v = itr.next(); 
                    if(parent[v]==0 && v!=1) {
                        parent[v] = u;
                    }
                    if(!visited[v]) 
                        stack.push(v); 
                } 

            } 
            for(int i = 0; i<order.size()-1; i+=2) {
                if(parent[order.get(i)]==order.get(i+1)) {
                    System.out.println(weight[order.get(i+1)][order.get(i)]);               
                }
                else {
                    System.out.println(weight[order.get(i)][order.get(i+1)]);               
                }
            }
        } 
    }

Answer 1

Для решения этой проблемы не требуется никакого специального алгоритма или структуры данных. Необходимо сделать только одно ключевое наблюдение:

• Если каждая вершина в вашем графе имеет степень 2 или меньше, то независимо от того, как вы размещаете вершины, всегда есть путь, который касается каждый край Следовательно, не имеет значения, как вы размещаете метки.

• Если в вашем графе есть хотя бы одна вершина со степенью 3 или более, мы можем разместить метки 0, 1 и 2 на ребрах, инцидентных общей вершине. Теперь максимальный минимальный экслюзант составляет 2, поскольку мы можем выбрать путь от 0 до 1. Совершенно очевидно, что вы не можете добиться большего успеха, чем это, поскольку вы всегда можете начать с 0 и go до 1, чтобы получить минимальное значение 2. Следовательно, вы можете сделать ребра 0, 1 и 2 инцидентными одной и той же вершине. Другие метки не имеют значения.