【白俊】14942アリ

18912 ワード
白駿 cpp boj 疎配列 テキストリンク
[正解ではなく解答記録]
蟻。
アリは眠りから覚め、穴の1番のノードに向かった.各ノードの移動可能距離が限られている場合、1番目のノードに最大限移動すると、各ノードは何番目のノードで停止しますか?

に近づく

  • 蟻穴はn個のノードとn−1本の幹線からなる樹構造である.
  • のすべてのノードから1番のノードに移動してみます.
  • 各ノードのエネルギー(移動可能距離)は限られている.
  • ノードは最大10万個で、1個ずつ移動できません.

    • インプリメンテーション


    疎配列


    [疎案が分かればスキップできる]
    1 -- 2 -- 3 -- 4 -- 5
    このように接続されたグラフィックがあり、5から3に移動します.
    5に移動した親4、4に移動した親3.
    このように親について上へ行く方法で移動することができます
    ふと思い出す
    親について行かないでください.もし私が両親を知っていたらどうなりますか.
    5->4->3ではなく、5の親が3を3に格納します.
    移動時に5->3に移動します.
    親の親とは言い難いが、次はn番目の親という.
    上の両親は最初の両親の両親は2番目の両親です
    保存しやすいテーブルを作成しましょう.
    table[0][i]は、i番ノードの最初の親ノードを格納する.
    2番目の親を格納するテーブル[1][n]は以下のように定義される.
    table[1][i] = table[0][table[0][i]]
    2番目の親はすぐに見つかるが、今のところよくないか分からない.
    でも今から4人目の両親を探しましょう
    4番目の両親は2番目の両親の2番目の両親です.
    table[1][i]は2番目の親です
    table[2][i]を書けばいいでしょう
    table[2][i] = table[1][table[2][i]]
    4番目の親に直接アクセスできるようになりました.
    これを繰り返すと8 16 32...2^nを使用すると、親に直接アクセスできます.
    3番目の親は2番目の親の1番目の親として訪問できるので、単独で保存することはありません.
    このときBeatで理解すると便利です
    5番目の親=5=101=4番目の親の最初の親
    7番目の親=7=111=4番目の親の最初の親
    8番目の親=8=1000=8番目の親
    これらの疎配列
    bfsまたはdfsを用いてテーブル[0][i]を予め取得すると仮定する.
    for (int i = 1; i <= 17; i++) {
		for (int j = 1; j <= n; j++) {
			table[i][j] = table[i-1][table[i-1][j]];

		}
}
    これらのコードを使用して初期化できます.

    蟻。


    疎アレイを使用すると、親ノードにすばやく登ることができます.
    そして、この問題では、エネルギーを考えなければなりません.
    したがって、疎配列を作成する場合、親ノードの番号が同じであるだけでなく、現在のノードから親ノードに至るまで、
    消費電力を保存するように変更することもできます.
    pairテーブル[18][100001]//親ノード、親ノードへの消費電力
    table[0][i]も同様にdfs、bfsを迂回し、最初の親ノードの番号と消費電力を記録する.
    void dfs(int node) {
	check[node] = true;
	for (int i = 0; i < v[node].size(); i++){
		if (!check[v[node][i].first]) {
			table[0][v[node][i].first] = { node,v[node][i].second };
			dfs(v[node][i].first);
		}
	}
}
    テーブル全体の初期化も次のように変更されます.
    for (int i = 1; i <= 17; i++) {
		for (int j = 1; j <= n; j++) {
			table[i][j].first = table[i-1][table[i-1][j].first].first;
			table[i][j].second = table[i - 1][table[i - 1][j].first].second + table[i - 1][j].second;
		}
	}
    今、蟻の穴から1番ノードへの旅の準備ができています.

    移動


    移動しよう
    現在のノードがiの場合、最も遠い親ノードから開始できるかどうかを確認します.
    if(table[17][i].second <= energy[i])
    nが2番目の親^(17−1)を持たない場合、0は0になる.
    したがって、0の場合は移動しない条件が追加されます.
    if(table[17][i].first != 0 && table[17][i].second <= energy[i])
    次に、i番ノードから2^(17-1)の2番目の親ノードに移動できない場合、2^(16-1)の2番目の親ノードに移動でき、2^(15-1)、2^(14-1)に移動できます.親と一緒に移動しても2^(17-1)より遠くは行けません.
    1000 > 0111
    したがって、親ノードのすべてのノードでの移動は、1つのリング17〜0の周りを回るだけでよい.
    次に、target=iとして親に従うように指定し、target=親に変更し、targetに基づいて移動します.
    int target = i;
for (int j = 17; j >= 0; j--) {
	if(table[17][i].first != 0 && table[17][i].second <= energy[i]) {
		target = table[j][target].first;
	}
}
    一方target=親に変更したエネルギー消費は、変更前のエネルギー消費を反映しません.
    したがってtarget=は親に変更され、移動するエネルギーを消費します.
    エネルギーは、変化するtargetではなく、所与のiに消費されなければならない.
    target = i;
for (int j = 17; j >= 0; j--) {
	if(table[17][i].first != 0 && table[17][i].second <= energy[i]) {
		energy[i] -= table[j][target].second;
		target = table[j][target].first;
	}
}
    最後に、この操作をノード1-nで繰り返し、親ノードに移動した後に答えを出力します.
    int target;
for(int i = 1;i <= n; i++)	
    target = i;
	for (int j = 17; j >= 0; j--) {
		if(table[17][i].first != 0 && table[17][i].second <= energy[i]) {
			energy[i] -= table[j][target].second;
			target = table[j][target].first;
		}
	}
    printf("%d",target);
}

    の最後の部分


    まばらな配列の練習にいい問題です
    終わりだ!
    オブジェクト属性のポインタの使い方
    SRM 585