有人可以提供一些如何解决问题的想法吗？Machines have once again attacked the kingdom of Xions. The kingdom of Xions has N cities and N-1 bidirectional roads. The road network is such that there is a unique path between any pair of cities.
Morpheus has the news that K Machines are planning to destroy the whole kingdom. These Machines are initially living in K different cities of the kingdom and anytime from now they can plan and launch an attack. So he has asked Neo to destroy some of the roads to disrupt the connection among Machines i.e after destroying those roads there should not be any path between any two Machines.
Since the attack can be at any time from now, Neo has to do this task as fast as possible. Each road in the kingdom takes certain time to get destroyed and they can be destroyed only one at a time.
You need to write a program that tells Neo the minimum amount of time he will require to disrupt the connection among machines.
Sample Input First line of the input contains two, space-separated integers, N and K. Cities are numbered 0 to N-1. Then follow N-1 lines, each containing three, space-separated integers, x y z, which means there is a bidirectional road connecting city x and city y, and to destroy this road it takes z units of time. Then follow K lines each containing an integer. Ith integer is the id of city in which ith Machine is currently located.
Output Format Print in a single line the minimum time required to disrupt the connection among Machines.
Sample Input
5 3 2 1 8 1 0 5 2 4 5 1 3 4 2 4 0Sample Output
10Explanation Neo can destroy the road connecting city 2 and city 4 of weight 5 , and the road connecting city 0 and city 1 of weight 5. As only one road can be destroyed at a time, the total minimum time taken is 10 units of time. After destroying these roads none of the Machines can reach other Machine via any path.
Constraints
2 <= N <= 100,000 2 <= K <= N 1 <= time to destroy a road <= 1000,000
双向生成树
6
我在interviewstreet.com发现了这个问题。
- user1374210
2
6个回答
3
这个王国有 N 个城市，N-1 条边并且完全连接，因此它是一棵树（在图论中）。在这张图片上，您可以看到输入图形的树表示，其中机器由红色顶点表示。
另外，您应该考虑从根节点到所有叶节点的所有路径。因此，在每条路径中，您将有几个红色节点，并且在删除边缘时，您只应考虑相邻的红色节点。例如，在路径0-10中，有两个有意义的对 - (0,3) 和 (3,10)。您必须从每条连接顶点成对的路径中恰好删除一个节点（不少也不多）。
希望这些建议对您有所帮助。
- hsestupin
2
你的图片与样本输入有什么关系？样本中有5个城市（和3台机器），而你的树要大得多。 - voidengine
1我并不打算让这张图片对应示例输入。这只是为了更好地理解我的建议而进行的说明。 - hsestupin
2
如他人所说，具有N个顶点和N-1条边的连通图是一棵树。
这种问题需要贪心算法的解决方法；我会采用Kruskal算法的修改版：
开始时有一个由N个组件组成的集合-每个节点（城市）有1个组件。跟踪哪些组件包含机器占领的城市。
每次选取一条边（道路），按降序排列权重（从最昂贵的道路开始摧毁）。对于这条边（必然连接两个组件-图是一棵树）：
- 如果两个相邻组件都包含机器占领的城市，则必须摧毁此道路，将其标记为已摧毁。 - 否则，将相邻的组件合并为一个组件。如果其中一个组件包含机器占领的城市，则合并后的组件也包含该城市。
完成所有边的处理后，返回摧毁道路的成本总和。
对于良好选择的数据结构和排序方法，复杂度将与Kruskal算法相同，即几乎是线性的。
这种问题需要贪心算法的解决方法；我会采用Kruskal算法的修改版：
开始时有一个由N个组件组成的集合-每个节点（城市）有1个组件。跟踪哪些组件包含机器占领的城市。
每次选取一条边（道路），按降序排列权重（从最昂贵的道路开始摧毁）。对于这条边（必然连接两个组件-图是一棵树）：
- 如果两个相邻组件都包含机器占领的城市，则必须摧毁此道路，将其标记为已摧毁。 - 否则，将相邻的组件合并为一个组件。如果其中一个组件包含机器占领的城市，则合并后的组件也包含该城市。
完成所有边的处理后，返回摧毁道路的成本总和。
对于良好选择的数据结构和排序方法，复杂度将与Kruskal算法相同，即几乎是线性的。
- voidengine
2
pjotr给出了一个正确的答案（虽然不是渐近最优解），但是这个语句
这种问题需要贪心算法来解决
确实需要证明，因为在现实世界中（与竞技编程区分开来），有几个这种“类型”的问题，贪心算法并不是最优解（例如一般图中的这个问题，称为多终端割，是NP难的）。在这种情况下，证明包括验证拟阵公理。令A ⊆ E是一个边集，如果图（V，E \ A）恰好有|A| + 1个包含至少一个机器的连通分量，则A是独立的。
空集的独立性。微不足道。
遗传属性。让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多1个，因此A ∪ {e}是独立的，如所需。
- wobble
1
1同意。有了一些经验，人们就会对这种简单问题应该使用什么方法有所感觉（在这里，我们称之为“看看方法”），但证明总是更好的。 - voidengine
2
所有三个答案都会导致正确的解决方案，但是你不能在interviewstreet.com提供的时间限制内实现解决方案。你需要考虑一些简单的方法来成功解决这个问题。
提示：从机器所在的节点开始。
- Anantha Krishnan
1
从任一台机器节点开始执行深度优先搜索（DFS）。同时，跟踪到目前为止遇到的最小权重边。一旦找到下一个也包含机器的节点，请删除到目前为止记录的最小边。现在从这个新节点开始DFS。 重复此过程，直到找到所有存在机器的节点。
这样应该是O（N）的方式！！
- Raghu
-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);
}
}
- GlacierKba6
1
我认为更好的做法是引导提问者自己解决问题，而不仅仅是复制粘贴代码。 - hcarver
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
N个顶点和N-1条边，并且图形仍然连接（没有“孤岛”），那么该图形是一条直线。 - Li-aung Yip