英文:
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<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)]);
}
}
}
}
答案1
得分: 1
没有特殊的算法或数据结构需要解决这个问题。只需要进行一个关键的观察:
-
如果图中的每个顶点的度数都不超过2,那么无论如何放置这些顶点,总是存在一条涵盖每条边的路径。因此,放置标签的方式并不重要。
-
如果图中至少有一个顶点的度数达到3或更多,我们可以将标签
0
、1
和2
放置在与一个公共顶点相连的边上。现在,最大的最小排除值是2
,因为我们可以从0
走到1
。很明显,你无法做得比这更好,因为你总可以从0
出发,前往1
,得到一个最小的排除值2
。因此,你可以让边上的标签分别为0
、1
和2
。其他的标签并不重要。
英文:
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
, and2
on edges incident to a common vertex. Now, the maximum minimum excludant is2
since we can take a path from0
to1
. It's pretty clear that you can't do better than this since you can always start at0
and go to1
to get a minimum excludant of2
. Therefore, you can make the edges0
,1
, and2
incident to the same vertex. The other labels don't matter.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论