まず第一に、この記事は最適化の詳細を学ぶために書かれたものであり、そのヒントはコメント欄に残してください。
タスクの状態と目的
タスクは非常に簡単です。
M市では、N個の新しいマイクロディストリクトが建設中であり、その間にM本の幹線道路が計画されています。 各道路には独自の建設費Pijがあります。 昨年、自治体はこれらのM道路からKユニットを建設することに成功しました。 残念ながら、今年は建設の資金を削減することが決定され、今では計画されているが建設されていないMK道路から、少なくとも1つのルートが任意の小地区から他の地区に存在するようにする必要がありますが、同時にそれらの建設のコストは最小限です（保証され、そのようなセットが存在すること）。
新しい計画の下で道路網の建設を完了するための最小コストPとは何ですか？
入力/出力
入力形式：
最初の行には2つのスペース文字が含まれています。
N（2≤N≤10 ^ 5）-建設中のマイクロ地区の数、
M（1≤M≤min（N（N-1）、2 * 10 ^ 6））-計画道路の数。
次のM行は、計画された道路を端の番号のペアでソートしたものであり、それぞれにスペースで区切られた3つの整数が含まれています。
i（1≤i <N）-道路が始まる小区域の番号、
j（i <j≤N）は、道路が終わる小区域の数です。
Pij（0≤Pij≤103）-道路建設のコスト。 道路が既に建設されている場合は0。
出力形式：
結論には、スペースで区切られた2つの数値を含める必要があります。新しい計画に従って道路網の建設を完了するための最小コストPと、その上に建設される道路の数です。
最初の行には2つのスペース文字が含まれています。
N（2≤N≤10 ^ 5）-建設中のマイクロ地区の数、
M（1≤M≤min（N（N-1）、2 * 10 ^ 6））-計画道路の数。
次のM行は、計画された道路を端の番号のペアでソートしたものであり、それぞれにスペースで区切られた3つの整数が含まれています。
i（1≤i <N）-道路が始まる小区域の番号、
j（i <j≤N）は、道路が終わる小区域の数です。
Pij（0≤Pij≤103）-道路建設のコスト。 道路が既に建設されている場合は0。
出力形式：
結論には、スペースで区切られた2つの数値を含める必要があります。新しい計画に従って道路網の建設を完了するための最小コストPと、その上に建設される道路の数です。
また、クラスカルアルゴリズム （最小スパニングツリーの構築）によって解決されます。 当初、コンテストの実行時間は2秒、メモリは24 MBに制限されていました。 真剣ではありません。 プログラムを可能な限り最適化し、最も複雑なテストで100ミリ秒を達成するという目標を設定しました。使用できるのはSTLライブラリと固定コンパイラ設定のみです（結局、これはコンテストのタスクです）。 タスクは最後まで完了しませんでした-122ミリ秒以内で11 MBのメモリを保持しました。 最もせっかちな人のために、プログラムコードを提供します。
プログラムコード
#include <iostream> #include <vector> #include <algorithm> /* * */ template <class T> struct Triplet { T first; // , T second; // , T third; // }; /* * UnionFind */ template <class T> class UF_element { public: T parent; // T size; // UF_element() {} UF_element(T id) : size(1) , parent(id) { } }; template <class T> class UnionFind { private: std::vector<UF_element<T>> Elements; public: /* * , */ UnionFind(T n) : Elements(n + 1) { for (register T i = 1; i < n + 1; ++i) { Elements[i] = UF_element<T>(i); } } /* * . * (log n), * O(1) */ T find(T id){ UF_element<T>& current = Elements[id]; while (current.parent != Elements[current.parent].parent){ current.parent = Elements[current.parent].parent; } return current.parent; } void merge(T a, T b) { UF_element<T>& UF_elem_A = Elements[find(a)]; UF_element<T>& UF_elem_B = Elements[find(b)]; if(UF_elem_A.parent == UF_elem_B.parent) return; if(UF_elem_A.size < UF_elem_B.size) { UF_elem_A.parent = b; UF_elem_B.size += UF_elem_A.size; } else { UF_elem_B.parent = a; UF_elem_A.size += UF_elem_B.size; } } }; template <typename T> bool comp(const Triplet<T>& a, const Triplet<T>& b) { return (a.third < b.third); } template <typename T> void kruskal(std::vector<Triplet<T>>& data, size_t& cost, size_t& count, const size_t& n) { UnionFind<T> N(n); for (size_t i = 0; i < data.size(); ++i) { if (N.find(data[i].first) != N.find(data[i].second)) { if (data[i].third) { // 0 (. ) cost += data[i].third; // ++count; // , } N.merge(data[i].first, data[i].second); } } } /* * */ template <typename T> void read_unlocked(T &out) { T c = getchar_unlocked(); for (; '0' <= c && c <= '9' ; c = getchar_unlocked()) { if (c == ' ' || c == '\n') return; out = out * 10 + c - '0'; } } int main() { std::ios_base::sync_with_stdio(false); size_t count = 0, cost = 0; // . @ilammy unsigned int n = 0, m = 0; read_unlocked(n); read_unlocked(m); std::vector<Triplet<unsigned int>> input(m); for (size_t i = 0; i < m; ++i) { read_unlocked(input[i].first); read_unlocked(input[i].second); read_unlocked(input[i].third); } std::sort(input.begin(), input.end(), comp<unsigned int>); kruskal(input, cost, count, n); std::cout << cost << " " << count << '\n'; }
データアライメント
ここでデータのアライメントについて詳しく知ることができます。具体的な例を示して説明します。 残念ながら、これはコードのどこでも明示的に使用されていませんが、次のような構造を見てみましょう。
struct A { char a; long int b; int c; };
この構造には24バイトが必要です（このため、sizeof（A）の結果を表示します）。
次に、この構造を検討します。
struct B { char a; int c; long int b; };
必要なのはわずか16バイトです。 なぜそう 実際、64ビットOSでは、メモリは8バイト単位で読み取られ、データは、特にクラスAのプロセッサの処理を高速化するために調整されます。メモリレイアウトは次のようになります。
（aの下に1バイト+空の7バイト）+（bの下に8バイト）+（cの下に4バイト+ 4つの空バイト）= 24バイト。
それほど経済的ではありませんか？ クラスBの場合、占有メモリは次のようになります。
（aの下に1バイト+ cの下に4バイト）+（bの下に8バイト）= 16バイト。
データを「前後に」移動するのは時間の価値があり、移動するデータが少ないほどプログラムが高速化されるため、このような些細なことに注意する価値があります。そして、2、3行を交換することは最も難しい最適化ではありません。
初期化リスト
コンストラクターが次のように見える理由：
UF_element(T id) : size(1) , parent(id) { }
そうではありません：
UF_element(T id) { size = 1; parent = id; }
ここで読むことができます 。 初期化リストを使用する場合、クラスフィールドに対してデフォルトコンストラクターが呼び出され、クラスの本体コンストラクターで割り当てが行われる2番目のケースとは異なり、渡された値でコンストラクターが呼び出されます。
レジスタ指定子
ちょっとした理論：
register-自動メモリクラスの指定子。 デフォルトでローカルメモリにあるオブジェクトに適用されます。 コンパイラーは、レジスター指定子で宣言されたオブジェクトの値を、ローカルメモリーではなく使用可能なレジスターのいずれかに配置することが「要求」 （オプション）です。
私のコードでは、この構成を使用しました。
for (register T i = 1; i < n + 1; ++i) { idElements[i] = UF_element<T>(i); }
この指定子を正しく使用してください。
1からnまでの数の配列をハンマーで打つ必要がある場合（上記の例のように）、指定子を使用すると速度が向上します。ループの本体がそれほど重要でない場合、レジスタはパフォーマンスを変更しないだけでなく、パフォーマンスを低下させる可能性があります。変数としてレジスタを強調表示します。
メモリを操作する
非常に短く、よく書かれています 。 一般に、プログラムがメモリをどのように使用するかを理解し始め、特にリークを探すと、いくつかのルールが作成されます。
私自身、1つのことを理解しました：プログラマーがnew演算子で割り当てられたメモリがいつどこで解放され、deleteを呼び出した後に解放されたメモリにアクセスするのがメモリマネージャにとってどれほど便利かを伝える立場にない限り、新規/削除。 したがって、beatられないように、これらの演算子のアーキテクチャ上の使用を取り除きました。
UnionFind(T n) : Elements(n + 1) // { for (register T i = 1; i < n + 1; ++i) { Elements[i] = UF_element<T>(i); // } }
データの入出力
この記事に沿って、入力が大幅に加速されました。 このタスクでは2つの数値しか出力されないため、putchar（putchar_unlocked）を使用しても大きな利益はありませんが、確認するまで信じない人のために、putchar_unlockedを使用した出力の実装を以下に示します。
出力機能
/* * : * - , * - , */ template <typename T> void write_unlocked(T inp, char last=' ') { if (!inp) { putchar_unlocked('0'); putchar_unlocked(last); return; } T out = 0; unsigned char sz_inp = 0; // for (; inp; inp /= 10, ++sz_inp) { out = (out << 3) + (out << 1) + inp % 10; } // for (; out; out /= 10, --sz_inp) { putchar_unlocked(out % 10 + '0'); } // , for (;sz_inp; --sz_inp) { putchar_unlocked('0'); } putchar_unlocked(last); }