Given a tree, assign weights to each edge in order to minimize the weight of every path (u, v) in the tree

huangapple go评论82阅读模式
英文:

Given a tree, assign weights to each edge in order to minimize the weight of every path (u, v) in the tree

问题

给定一棵树,为每条边分配权重,以使树中的每条路径 (u, v) 的权重之和最小。为了澄清,我们要使得树中每条路径上的最大权重最小化。

这个问题能用某种数据结构或算法解决吗?你如何确定在树的每条边上放置哪些权重?输入是一个数字 N,你必须在树的每条边上的值范围 [0, N-2](包括边界)之间放置权重。

让我澄清一下这个问题。假设你有一条边 (1, 2),你在那条边上放置权重 3。在问题的背景下,“权重”的实际定义是从 [0, N-2] 中不存在于路径 (u, v) 上的最小值。即使特定边上的权重是三,问题背景下的实际权重是零。此外,该问题中树的根节点是 1。

我最初的解决方法是将 [0, N-2] 的值(我们可以分配给每条边的权重值)添加到堆栈中,然后使用深度优先搜索遍历树,并从堆栈中弹出一个值(最大的边值),然后将其分配给该边。然而,这并不能最小化所有路径的成本。请记住,成本是从路径 (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)]);               
           }
       }
   } 
}
英文:

>Given a tree, assign weights to each edge in order to minimize the weight of every path (u, v) in the tree. To clarify, we are minimizing the maximum weight on every path in the tree
>
>Can this question be solved with some sort of data structure or algorithm? How do you determine which weights to place on each edge in the tree? The input is a number N, and you have to place weights in between the values of [0, N-2] (inclusive) on each edge of the tree.

Let me clarify the question. Let's say you have an edge (1, 2) and you place weight 3 on that edge. The actual definition of "weight" in the context of the question is the minimum-most value from [0, N-2] that IS NOT present on the path from (u, v). Even though the weight on the specific edge is three, the actual weight in the context of the question is zero. Also, the root of the tree in this question is 1.

My original approach for this question was to add the values from [0, N-2] (the edge values we can assign to each edge) to a stack, then traverse the tree using DFS and pop a value from the stack (the maximum-most edge value) and assign it to the edge. This, however, does not minimize the cost over all paths. Keep in mind, the cost is the minimum-most value not present on the path from (u, v). We are trying to place the costs to minimize the costs on every possible path.

My code:

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&lt;Integer&gt;[] adj = new LinkedList[n+1];
ArrayList&lt;Integer&gt; v = new ArrayList&lt;Integer&gt;(n+1);
for(int i = 1; i&lt;=n; i++) {
adj[i] = new LinkedList&lt;Integer&gt;();
}
for(int i = 0; i&lt;n-1; i++) {
String [] edge = (b1.readLine()).split(&quot; &quot;);
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&lt;Integer&gt; adj[], int u, int n, ArrayList&lt;Integer&gt; order)   { 
Stack&lt;Integer&gt; values = new Stack&lt;&gt;();
int [][] weight = new int[n+1][n+1];
for(int i = 0; i&lt;n-1; i++) {
values.push(i);
}
boolean [] visited = new boolean[n+1];
int [] parent = new int[n+1];
for (int i = 1; i &lt; n+1; i++) 
visited[i] = false; 
Stack&lt;Integer&gt; stack = new Stack&lt;&gt;(); 
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&lt;Integer&gt; itr = adj[u].iterator(); 
while (itr.hasNext())  {                    
int v = itr.next(); 
if(parent[v]==0 &amp;&amp; v!=1) {
parent[v] = u;
}
if(!visited[v]) 
stack.push(v); 
} 
} 
for(int i = 0; i&lt;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)]);               
}
}
} 
}

答案1

得分: 1

没有特殊的算法或数据结构需要解决这个问题。只需要进行一个关键的观察:

  • 如果图中的每个顶点的度数都不超过2,那么无论如何放置这些顶点,总是存在一条涵盖每条边的路径。因此,放置标签的方式并不重要。

  • 如果图中至少有一个顶点的度数达到3或更多,我们可以将标签 012 放置在与一个公共顶点相连的边上。现在,最大的最小排除值是 2,因为我们可以从 0 走到 1。很明显,你无法做得比这更好,因为你总可以从 0 出发,前往 1,得到一个最小的排除值 2。因此,你可以让边上的标签分别为 012。其他的标签并不重要。

英文:

There's no special algorithm or data structure that you need to solve this problem. There is just one key observation you need to make:

  • If every vertex in your graph has degree 2 or less, then no matter how you place the vertices, there's always a path that touches every edge. Therefore, it doesn't matter how you place the labels.

  • If there's at least one vertex in your graph with degree 3 or more, then we can place the labels 0, 1, and 2 on edges incident to a common vertex. Now, the maximum minimum excludant is 2 since we can take a path from 0 to 1. It's pretty clear that you can't do better than this since you can always start at 0 and go to 1 to get a minimum excludant of 2. Therefore, you can make the edges 0, 1, and 2 incident to the same vertex. The other labels don't matter.

huangapple
  • 本文由 发表于 2020年3月16日 03:26:37
  • 转载请务必保留本文链接:https://go.coder-hub.com/60696759.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定