Двунаправленный покрывающее дерево

Question

Я наткнулся на этот вопрос от interviewstreet.com

Машины вновь напали на королевство Xions. Королевство города Сион имеет N городов и N-1 двунаправленных дорог. Дорожная сеть - , так что между любыми парами городов существует уникальный путь.

У Morpheus есть новости, что K Machines планируют уничтожить все королевство . Эти машины изначально проживают в K разных городах города, и в любое время они могут планировать и запускать атаку . Поэтому он попросил Нео уничтожить некоторые из дорог, чтобы сорвать связь между машинами i.e после разрушения этих дорог там не должно быть никакого пути между любыми двумя машинами.

Поскольку атака может быть в любое время с этого момента, Нео должен выполнить эту задачу как можно быстрее. Каждая дорога в королевстве занимает определенное время до , и они могут быть уничтожены только по одному за раз.

Вам необходимо написать программу, которая сообщит Neo о минимальном количестве времени , который потребует нарушения связи между машинами.

Пример ввода Первая строка ввода содержит два разделенных пробелами целых чисел , N и K. Города нумеруются от 0 до N-1. Затем следуйте за N-1 строками, каждая из которых содержит три целых числа с пробелами, x y z, которые означает, что существует двунаправленная дорога, соединяющая города x и город y, и , чтобы уничтожить эту дорогу, она занимает z единиц времени. Затем следуют K строк , каждый из которых содержит целое число. Ith integer - это идентификатор города, в котором находится Машина.

Формат вывода Печать в одной строке минимальное время, необходимое для , нарушает соединение между машинами.

Пример ввода

5 3 
2 1 8 
1 0 5 
2 4 5 
1 3 4 
2 
4 
0 

Пример вывода

10 

Объяснение Neo может разрушить дорогу, связывающую город 2 и город 4 из веса 5, и дорога, соединяющая город 0 и город 1 веса 5. Как только одна дорога может быть уничтожена за раз, общее минимальное время, принятое - 10 единиц времени. После разрушения этих дорог ни одна из Машины не может добраться до другой машины по любому пути.

Ограничения

2 <= N <= 100,000 
2 <= K <= N 
1 <= time to destroy a road <= 1000,000 

Может кто-то идею, как подойти к решению.

Answer 1

Все три ответа приведут к правильному решению, но вы не можете достичь решения в течение срока, предоставленного интервьюучастником. Вы должны придумать какой-то простой подход для успешного решения этой проблемы.

СОВЕТ: начните с узла, где находится машина.

Answer 2

Царство есть N городов, N-1 ребро, и это полностью связано, поэтому наше царство tree (в теории графов). На этом изображении вы можете увидеть древовидное представление вашего входного графика, в котором машины представлены красными вершинами.

Кстати, вы должны рассмотреть все пути от корневой вершины ко всем листовым узлам. Таким образом, на каждом пути у вас будет несколько красных узлов, а при удалении краев вы должны учитывать только соседние красные узлы. Например, на пути 0-10 есть две значащие пары - (0,3) и (3,10). И вы должны удалить ровно один узел (не менее, не более) с каждого пути, который соединяет вершины в парах.

Я надеюсь, что этот совет был полезен.

Answer 3

Как говорят другие, связный граф с N вершинами и краями N-1 является деревом.

Этот вид проблемы требует жадного решения; Я бы сделал модификацию Kruskal's algorithm:

Начать с набора из N компонентов - по 1 для каждого узла (города). Следите за тем, какие компоненты содержат город, занятый машиной.

Возьмите 1 край (дорога) за раз, закажите по убыванию веса (начиная с дорог, наиболее дорогостоящих для уничтожения). Для этого края (который обязательно соединяет два компонента - граф является деревом):

• если оба neigboring компоненты содержат машинно занимаемого город, эта дорога должна быть уничтожена, пометить его как такой
• иначе, слияние сопутствующие компоненты в единицу. Если один из них содержит город, занятый машиной, то и объединенный компонент.

Когда вы закончите со всеми краями, верните сумму затрат на разрушенные дороги.

Сложность будет такой же, как алгоритм Крускаля, то есть почти линейный для хорошо подобранной структуры данных и метода сортировки.

Answer 4

Pjotr ​​имеет правильный ответ (хотя и не вполне асимптотический оптимальные), но это утверждение

Эта проблема требует для жадного решения

действительно требует доказательств, как и в реальном мире (в отличие от конкурентного программирования), существует несколько проблем этого вида “ вида ”, для которого жадное решение не является оптимальным (например, эта же проблема в общих графиках, которая называется многотерминальным разрезом d является NP-твердым). В этом случае доказательство состоит в проверке аксиом matroid. Пусть множество ребер A & subseteq; E be независимо, если график (V, E & setminus; A) имеет точно | A | + 1 компонент, содержащий по меньшей мере одну машину.

Независимость пустого набора. Тривиальный.

Наследственный. Пусть A - независимый набор. Каждое ребро e ∈ A соединяет две связанные компоненты графика (V, E & setminus; A), и каждый подключенный компонент содержит по крайней мере одну машину. При возвращении e на график количество подключенных компонентов, содержащих по меньшей мере одну машину, уменьшается на 1, поэтому A & setminus; {e} также является независимым.

Augmentation property. Пусть A и B - независимые множества с | A | < | B |. Поскольку (V, E & setminus; B) имеет более связанные компоненты, чем (V, E & setminus; A), по принципу голубины существует пара машин u, v такая, что u и v несвязны с помощью B, но не через A. Поскольку существует ровно один путь от u до v, B содержит по крайней мере одно ребро e на этом пути, и A не может содержать e. Удаление A ∪ {e} вызывает еще один компонент связи, содержащий по меньшей мере одну машину, чем A, поэтому A ∪ {e} является независимым, если требуется.

Answer 5

Я пишу код и вставляю все тесты.

#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); 
} 
} 

Answer 6

Запустить выполнение DFS с любого из узлов машины. Кроме того, отслеживайте края с минимальным весом, обнаруженным до сих пор. Как только вы найдете следующий узел, который также содержит машину, удалите минимальный край, записанный до сих пор. Начните DFS с этого нового узла. Повторяйте, пока не найдете все узлы, где существуют машины.

Должно быть, это O (N)!