Двунаправленное остовное дерево
Я сталкивался с этим вопросом от интервью street.com
Машины в очередной раз напали на королевство Сион. Королевство Сион имеет N городов и N-1 двунаправленных дорог. Дорожная сеть такова, что между любой парой городов существует уникальный путь.
У Морфеуса есть новость, что K Machines планируют уничтожить все королевство. Эти Машины изначально живут в К разных городах королевства, и в любое время они могут планировать и начинать атаку. Поэтому он попросил Нео уничтожить некоторые дороги, чтобы нарушить связь между машинами, т.е. после разрушения этих дорог не должно быть никакого пути между любыми двумя машинами.
Поскольку атака может быть в любое время, Neo должен выполнить эту задачу как можно быстрее. Каждая дорога в королевстве требует определенного времени, чтобы разрушиться, и они могут быть разрушены только по одному за раз.
Вам нужно написать программу, которая сообщает Neo минимальное количество времени, которое ему потребуется для разрыва соединения между машинами.
Образец ввода Первая строка ввода содержит два целых числа, разделенных пробелами, N и K. Города пронумерованы от 0 до N-1. Затем следуйте N-1 строкам, каждая из которых содержит три разделенных пробелом целых числа, x y z, что означает, что существует двунаправленная дорога, соединяющая город x и город y, и для разрушения этой дороги требуется z единицы времени. Затем следуйте K строкам, каждая из которых содержит целое число. I-е целое число - это идентификатор города, в котором сейчас находится i-я машина.
Формат вывода Выведите в одной строке минимальное время, необходимое для разрыва соединения между машинами.
Пример ввода
5 3 2 1 8 1 0 5 2 4 5 1 3 4 2 4 0Пример вывода
10Пояснение. Нео может разрушить дорогу, соединяющую город 2 и город 4 с весом 5, и дорогу, соединяющую город 0 и город 1 с весом 5. Поскольку за один раз может быть уничтожена только одна дорога, общее минимальное время, затраченное на это, составляет 10 единиц времени., После уничтожения этих дорог ни одна из Машин не сможет добраться до другой Машины любым путем.
Ограничения
2 <= N <= 100,000 2 <= K <= N 1 <= time to destroy a road <= 1000,000
Может кто-нибудь дать представление, как подойти к решению.
6 ответов
Все три ответа приведут к правильному решению, но вы не сможете найти решение в течение срока, указанного на сайте viewstreet.com. Вам нужно подумать о каком-то простом подходе, чтобы успешно решить эту проблему.
СОВЕТ: начать с узла, где присутствует машина.
В королевстве есть N городов, N-1 ребер, и оно полностью связано, поэтому наше королевство - дерево (в теории графов). На этом рисунке вы можете увидеть древовидное представление вашего входного графа, в котором машины представлены красными вершинами.
Кстати, вы должны рассмотреть все пути от корневой вершины до всех листовых узлов. Таким образом, на каждом пути у вас будет несколько красных узлов, и при удалении ребер следует учитывать только соседние красные узлы. Например, в пути 0-10 есть две значащие пары - (0,3) и (3,10). И вы должны удалить ровно один узел (не меньше, не больше) из каждого пути, который соединял вершины попарно.
Я надеюсь, что этот совет был полезен.
Петр имеет правильный ответ (хотя и не совсем асимптотически оптимальный), но это утверждение
Такая проблема требует жадного решения
действительно требует доказательств, так как в реальном мире (в отличие от конкурентного программирования) есть несколько проблем такого рода, для которых жадное решение не является оптимальным (например, эта та же самая проблема в общих графах, которая называется многотерминальным разрезом). и NP-жесткий). В этом случае доказательство состоит в проверке аксиом матроида. Пусть множество ребер A ⊆ E будет независимым, если граф (V, E ∖ A) имеет точно |A| + 1 связанных компонентов, содержащих хотя бы одну машину.
Независимость от пустого набора. Trivial.
Наследственное имущество. Пусть A - независимое множество. Каждое ребро e ∈ A соединяет две связные компоненты графа (V, E ∖ A), и каждая связная компонента содержит хотя бы одну машину. Возвращая e на график, количество связанных компонентов, содержащих хотя бы одну машину, уменьшается на 1, поэтому A ∖ {e} также не зависит.
Свойство увеличения. Пусть A и B - независимые множества с | A | <| B |. Так как (V, E ∖ B) имеет больше связных компонент, чем (V, E ∖ A), существует по принципу голубя дыра такая пара u, v, что u и v разъединены B, но не A. Так как это ровно один путь от u до v, B содержит хотя бы одно ребро e на этом пути, а A не может содержать e. Удаление A ∪ {e} индуцирует еще один связанный компонент, содержащий по крайней мере одну машину, чем A, поэтому A e {e} является независимым, как требуется.
Как говорят другие, связный граф с N вершинами и N-1 ребрами является деревом.
Такая проблема требует жадного решения; Я бы пошел на модификацию алгоритма Крускала:
Начните с набора из N компонентов - 1 для каждого узла (города). Следите за тем, какие компоненты содержат занятый машиной город.
Возьмите 1 ребро (дорогу) за раз, упорядочиваясь по убыванию веса (начиная с дорог, наиболее дорогих для разрушения). Для этого ребра (которое обязательно связывает два компонента - граф представляет собой дерево):
- если оба соседних компонента содержат населенный город, эта дорога должна быть уничтожена, отметьте ее как таковую
- в противном случае объедините соседние компоненты в один. Если один из них содержал город, занятый машиной, то же самое относится и к объединенному компоненту.
Когда вы закончите со всеми краями, верните сумму затрат на разрушенные дороги.
Сложность будет такой же, как у алгоритма Крускала, то есть почти линейная для правильно выбранной структуры данных и метода сортировки.
Начните выполнять DFS с любого из узлов машины. Кроме того, следите за краем с минимальным весом, встреченным до сих пор. Как только вы найдете следующий узел, который также содержит машину, удалите записанное минное ребро. Запустите DFS с этого нового узла сейчас. Повторяйте, пока не найдете все узлы, где существуют машины.
Должно быть из O(N) таким образом!
Я написал некоторый код и вставил все тесты.
#include <iostream>
#include<algorithm>
using namespace std;
class Line {
public:
Line(){
begin=0;end=0; weight=0;
}
int begin;int end;int weight;
bool operator<(const Line& _l)const {
return weight>_l.weight;
}
};
class Point{
public:
Point(){
pre=0;machine=false;
}
int pre;
bool machine;
};
void DP_Matrix();
void outputLines(Line* lines,Point* points,int N);
int main() {
DP_Matrix();
system("pause");
return 0;
}
int FMSFind(Point* trees,int x){
int r=x;
while(trees[r].pre!=r)
r=trees[r].pre;
int i=x;int j;
while(i!=r) {
j=trees[i].pre;
trees[i].pre=r;
i=j;
}
return r;
}
void DP_Matrix(){
int N,K,machine_index;scanf("%d%d",&N,&K);
Line* lines=new Line[100000];
Point* points=new Point[100000];
N--;
for(int i=0;i<N;i++) {
scanf("%d%d%d",&lines[i].begin,&lines[i].end,&lines[i].weight);
points[i].pre=i;
}
points[N].pre=N;
for(int i=0;i<K;i++) {
scanf("%d",&machine_index);
points[machine_index].machine=true;
}
long long finalRes=0;
for(int i=0;i<N;i++) {
int bP=FMSFind(points,lines[i].begin);
int eP=FMSFind(points,lines[i].end);
if(points[bP].machine&&points[eP].machine){
finalRes+=lines[i].weight;
}
else{
points[bP].pre=eP;
points[eP].machine=points[bP].machine||points[eP].machine;
points[bP].machine=points[eP].machine;
}
}
cout<<finalRes<<endl;
delete[] lines;
delete[] points;
}
void outputLines(Line* lines,Point* points,int N){
printf("\nLines:\n");
for(int i=0;i<N;i++){
printf("%d\t%d\t%d\n",lines[i].begin,lines[i].end,lines[i].weight);
}
printf("\nPoints:\n");
for(int i=0;i<=N;i++){
printf("%d\t%d\t%d\n",i,points[i].machine,points[i].pre);
}
}