6

我从 interviewstreet.com 遇到了这个问题

机器再次袭击了锡安王国。锡安王国有N座城市，N-1条双向道路。道路网络使得任何一对城市之间都有一条独特的路径。

Morpheus 得知 K Machines 计划摧毁整个王国的消息。这些机器最初生活在王国的 K 个不同城市，从现在开始，他们可以随时计划并发动攻击。所以他要求 Neo 破坏一些道路以破坏机器之间的连接，即在破坏这些道路之后，任何两台机器之间都不应该有任何路径。

由于攻击可能发生在从现在开始的任何时间，Neo 必须尽快完成这项任务。王国中的每条道路都需要一定的时间才能被摧毁，一次只能摧毁一条。

您需要编写一个程序，告诉 Neo 中断机器之间的连接所需的最短时间。

示例输入 输入的第一行包含两个以空格分隔的整数 N 和 K。城市编号为 0 到 N-1。然后沿着 N-1 行，每行包含三个空格分隔的整数 xyz，这意味着有一条双向道路连接城市 x 和城市 y，摧毁这条道路需要 z 个单位的时间。然后跟随 K 行，每行包含一个整数。第 i 个整数是第 i 个机器当前所在城市的 id。

输出格式 在一行中打印中断机器之间连接所需的最短时间。

样本输入 

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

有人可以给出如何处理解决方案的想法。

4

6 回答 6

2

树

这个王国有 N 个城市，N-1 条边并且它是完全连接的，因此我们的王国是树（在图论中）。在这张图片中，您可以看到输入图的树形表示，其中机器由红色顶点表示。

顺便说一句，您应该考虑从根顶点到所有叶节点的所有路径。因此，在每条路径中，您都会有几个红色节点，并且在删除边缘期间，您应该只考虑相邻的红色节点。例如，在路径 0-10 中有两个有意义的对 - (0,3) 和 (3,10)。并且您必须从成对连接顶点的每条路径中准确删除一个节点（不少于，不少于）。

我希望这个建议是有帮助的。

于 2012-05-04T07:55:09.050 回答
2

正如其他人所说，具有 N 个顶点和 N-1 条边的连通图是一棵树。

这类问题需要一个贪婪的解决方案；我会修改Kruskal 的算法：

从一组 N 个组件开始 - 每个节点（城市）1 个。跟踪哪些组件包含机器占用的城市。

一次取 1 条边（道路），按重量降序排列（从破坏成本最高的道路开始）。对于这条边（它必然连接两个组件 - 图是一棵树）：

  • 如果两个相邻的组件都包含一个机器占领的城市，这条路必须被摧毁，这样标记它
  • 否则，将相邻组件合并为一个。如果其中一个包含机器占用的城市，那么合并的组件也是如此。

完成所有边后，返回被毁道路的成本总和。

复杂性将与 Kruskal 算法相同，即对于精心选择的数据结构和排序方法而言几乎是线性的。

于 2012-05-04T09:39:08.937 回答
2

pjotr 有一个正确的答案（虽然不是渐近最优的），但是这个陈述

这类问题需要贪婪的解决方案

确实需要证明，因为在现实世界中（与竞争性编程不同），有几个这类问题的贪婪解决方案不是最优的（例如，在一般图中，这个非常相同的问题，称为多端割并且是 NP 难的）。在这种情况下，证明包括验证拟阵公理。如果图 (V, E ∖ A) 恰好有 |A|，则令一组边 A ⊆ E 是独立的 + 1 个包含至少一台机器的连接组件。

空集的独立性。琐碎的。

世袭财产。设 A 为独立集。每条边 e ∈ A 连接图的两个连通分量 (V, E ∖ A)，并且每个连通分量至少包含一台机器。将 e 放回图中，包含至少一台机器的连通分量的数量减少了 1，因此 A ∖ {e} 也是独立的。

增强属性。设 A 和 B 是具有 |A| 的独立集 < |乙|。由于 (V, E ∖ B) 比 (V, E ∖ A) 具有更多的连通分量，根据鸽巢原理存在一对机器 u, v 使得 u 和 v 被 B 断开但不被 A 断开。因为有恰好是一条从u到v的路径，B在这条路径上至少包含一条边e，A不能包含e。删除 A ∪ {e} 会导致比 A 多一个包含至少一台机器的连接组件，因此 A ∪ {e} 根据需要是独立的。

于 2012-05-04T11:56:14.187 回答
2

所有三个答案都会导致正确的解决方案，但您无法在 interviewstreet.com 提供的时限内得到解决方案。你必须想一些简单的方法来成功地解决这个问题。

提示：从机器所在的节点开始。

于 2012-05-07T13:23:08.517 回答
0

从任一机器节点开始执行 DFS。此外，跟踪到目前为止遇到的最小权重的边缘。一旦你找到下一个包含机器的节点，就删除目前记录的最小边。现在从这个新节点启动 DFS。重复直到找到机器所在的所有节点。

应该是 O(N) 那样！

于 2012-11-04T00:43:25.370 回答
-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);
}
}
于 2012-09-23T03:03:11.433 回答