I was solving some graph problems with dp and bitmasking when a problem crossed my mind. But I'm unable to solve it optimally. I tried brute force considering all possible combinations. Can we form an optimal solution?
The problem goes like this:
SPECIAL node : Can connect upto 10 nodes.
GOOD node: Is only connected to exactly 1
SPECIAL node and no other node.
VALID edge: Has atleast one
VALID graph: A connected graph such that every edge is a
VALID edge and each node is either a
GOOD node or a
Given a connected graph with
N nodes (including a
source node), your task is to:
- Delete 0 or more edges such that the graph becomes a
- And the sum of distances from all nodes to source node is minimum.
- And the number of
SPECIAL nodesis minimum possible.
- Graph is undirected.
- It is always possible to connect all nodes.
- Minimisation of sum has higher priority than minimisation of
1<N<=30 1<=E<=435 1<=src<=30
N -> total number of nodes
E edges with values:
u v w (there is an edge between u and v with length w)
src -> index of source node