数時間から次の問題を試していますが、正しいロジックを取得できません。
あなたは、補助送電網の配置を担当する計画チームに所属しています。この補助グリッドの目的は、停電の場合に小さな町のジャンクションにある街灯柱に電力を供給することです。あなたのチームには k 個のジェネレーターが与えられます。これらのジェネレーターはグリッド内のどこにでも配置でき、各ジェネレーターはグリッドを介して接続されているすべてのランプをオンにすることができます (パスが存在します)。街中の道路ごとに、その道路の終点にある 2 つのジャンクションを接続するために送電網にケーブルを敷設するコストが与えられます。町のレイアウトを考えると、最小コスト グリッドを配置し、その上に発電機を設置して、町のジャンクションにあるすべての街灯柱を点灯できるようにする必要があります。
入力: 最初の行には、ケース数 t が含まれています。次に、t ケースが続きます。各ケースの最初の行には、3 つの整数 n、m、および k が含まれています。ジャンクションには 1 から n までの番号が付けられています。その後、m 行が続きます。各行には 3 つの整数 i、j、c が含まれます。整数 i と j は 1 から n の間で、道路の 2 つの端点にある 2 つのジャンクションを示します。3 番目の整数 c は、この道路のグリッドにケーブルを敷設するコストです。
出力: ケースごとに 1 行ずつ、t 行を出力する必要があります。ケースごとに最小コスト グリッドを出力します。このタスクが不可能な場合 (つまり、k 個のジェネレーターですべてのランプをオンにする方法がない場合)、"Impossible!" を出力します。（わかりやすくするために引用）
Constraints:
1 <= t <= 25
1 <= n <= 2000
0 <= m <= n(n-1)/2
0 <= c <= 1000000
Sample Input:
2
3 1 1
1 2 10
6 7 2
1 2 20
1 3 5
1 4 10
2 3 8
2 4 15
3 4 2
5 6 9
Sample Output:
Impossible!
24
説明: 最初のケースでは、ジャンクション 1 と 2 がジャンクション 3 から切り離されており、1 つの発電機だけですべての街灯を点けることはできません。少なくとも 2 つの発電機が必要です。2 番目のケースでは、道路 (1 3)、(2 3)、(3 4)、および (5 6) にケーブルを敷設し、ジャンクション 1 に発電機を 1 つ、ジャンクション 1 に発電機を 1 つ設置できます。ジャンクション5の発電機。
この問題を効率的に解決するにはどうすればよいでしょうか?今のところ、BruteForce 以外に考えがありません。変更されたクルスカルはここで機能しますか?