algorithm - 双方向スパニング ツリー

Question

この質問は、interviewstreet.com から見つけました。

マシンが再びシオンの王国を攻撃しました。Xions 王国には、N 個の都市と N-1 個の双方向道路があります。道路網は、都市の任意のペア間に固有の経路があるようなものです。

モーフィアスは、K マシーンが王国全体を破壊する計画を立てているというニュースを受け取りました。これらのマシンは当初、王国の K 個の異なる都市に住んでおり、いつでも攻撃を計画して開始できます。そのため、彼はネオにいくつかの道路を破壊してマシン間の接続を中断するように依頼しました。つまり、これらの道路を破壊した後は、2 つのマシン間にパスがあってはなりません。

攻撃は今からいつでも可能であるため、ネオはこのタスクをできるだけ早く実行する必要があります. 王国の各道路は破壊されるまでに一定の時間がかかり、一度に 1 つしか破壊できません。

マシン間の接続を切断するのに必要な最小時間を Neo に伝えるプログラムを作成する必要があります。

サンプル入力 入力の最初の行には、スペースで区切られた 2 つの整数 N と K が含まれます。都市には 0 から N-1 の番号が付けられます。次に、それぞれがスペースで区切られた 3 つの整数 xyz を含む N-1 行をたどります。これは、都市 x と都市 y を結ぶ双方向の道路があることを意味し、この道路を破壊するには z 単位の時間がかかります。次に、それぞれが整数を含む K 行をたどります。i 番目の整数は、i 番目の Machine が現在位置している都市の ID です。

出力形式 マシン間の接続を中断するのに必要な最小時間を 1 行で出力します。

サンプル入力

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

サンプル出力

10

説明 Neo と重み 5 の都市 2 と都市 4 を結ぶ道路、および重み 5 の都市 0 と都市 1 を結ぶ道路を破壊できます。一度に破壊できる道路は 1 本だけなので、合計で最小時間は 10 単位時間です。 . これらの道路を破壊した後、マシンはどのパスからでも他のマシンに到達できなくなります。

制約

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

誰かが解決策にアプローチする方法を教えてもらえますか?

Answer 1

他の人が言ったように、N 個の頂点と N-1 個の辺を持つ連結グラフはツリーです。

この種の問題は貪欲な解決策を求めます。Kruskal のアルゴリズムの修正を行います。

各ノード (都市) に対して 1 つの N コンポーネントのセットから始めます。機械が占有する都市を含むコンポーネントを追跡します。

一度に 1 つのエッジ (道路) を取り、重みの降順に並べます (破壊するのに最もコストがかかる道路から始めます)。この辺 (必然的に 2 つのコンポーネントを接続します - グラフはツリーです):

• 隣接するコンポーネントの両方に機械が占有する都市が含まれている場合、この道路を破壊する必要があります。そのようにマークしてください。
• それ以外の場合は、隣接するコンポーネントを 1 つにマージします。それらの 1 つに機械が占有する都市が含まれていた場合、マージされたコンポーネントも同様です。

すべてのエッジを処理し終わったら、破壊された道路のコストの合計を返します。

複雑さは Kruskal のアルゴリズムと同じになります。つまり、適切に選択されたデータ構造と並べ替え方法に対してほぼ線形になります。

Answer 2

3 つの答えはすべて正しい解決策につながりますが、interviewstreet.com が提供する制限時間内に解決策を達成することはできません。この問題をうまく解決するには、簡単な方法を考えなければなりません。

ヒント: マシンが存在するノードから開始します。

Answer 3

pjotr には正しい答えがあります (ただし、漸近的に最適というわけではありません) が、このステートメントは

この種の問題は貪欲な解決策を求めます

現実の世界では (競技プログラミングとは区別されるように) 、貪欲なソリューションが最適ではないこの「種類」の問題がいくつかあるため、実際には証明が必要です(たとえば、マルチターミナル カットと呼ばれる、一般的なグラフでのこのまったく同じ問題です)。 NP 困難です)。この場合、証明はマトロイドの公理を検証することから成ります。グラフ(V, E ∖ A) が正確に |A | + 少なくとも 1 台のマシンを含む 1 つの接続コンポーネント。

空集合の独立性。些細なこと。

遺伝財産。A を独立集合とします。すべてのエッジ e ∈ A はグラフの 2 つの連結要素 (V, E ∖ A) を結合し、すべての連結要素には少なくとも 1 つのマシンが含まれます。e をグラフに戻すと、少なくとも 1 つのマシンを含む連結要素の数が 1 減少するため、A ∖ {e} も独立しています。

増強プロパティ。A と B を |A| の独立集合とする。< |B|。(V, E ∖ B) には (V, E ∖ A) よりも多くの連結成分があるため、ピジョンホールの原理により、u と v が B によって切断され、A によって切断されないマシンのペア u、v が存在します。は u から v への 1 つのパスであり、B はこのパス上に少なくとも 1 つのエッジ e を含み、A は e を含むことはできません。A ∪ {e} を削除すると、A よりも少なくとも 1 つのマシンを含む連結成分がもう 1 つ誘導されるため、A ∪ {e} は必要に応じて独立しています。

Answer 4

The kingdom has N cities, N-1 edges and it's fully connected, therefore our kingdom is tree (in graph theory). At this picture you can see tree representation of your input graph in which Machines are represented by red vertices.

By the way you should consider all paths from the root vertex to all leaf nodes. So in every path you would have several red nodes and during removing edges you should take in account only neighboring red nodes. For example in path 0-10 there are two meaningfull pairs - (0,3) and (3,10). And you must remove exactly one node (not less, not more) from each path which connected vertices in pairs.

I hope this advice was helpful.

Answer 5

いずれかのマシン ノードから DFS の実行を開始します。また、これまでに遭遇した最小の重みでエッジを追跡します。マシンも含む次のノードを見つけたらすぐに、これまでに記録された最小エッジを削除します。この新しいノードから DFS を開始します。マシンが存在するすべてのノードが見つかるまで繰り返します。

そのようにO（N）でなければなりません!!

Answer 6

コードを書いて、すべてのテストを貼り付けました。

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