[プログラマー]#42861島を接続

13134 ワード
プログラマ kruskal algorithm MST テキストリンク

質問する


n個の島の間に橋を建設する費用(費用)については、すべての島が最小の費用で互いに通行できるようにする解決策を完了し、必要な最小の費用を返してください.
橋を何度も渡っても、たどり着けば通行できます.例えば、A島とB島の間に橋があり、B島とC島の間に橋があれば、A島とC島は互いに通行することができる.

せいげんじょうけん

  • 島の個数nは1以上100以下である.
  • コストの長さは(n−1)*n)/2以下である.
  • の任意iについては、コスト[i][0]とコスト[i][1]は、橋を結ぶ2つの島の番号を含み、コスト[i][2]は、この2つの島を結ぶ橋を建設するのに必要な費用である.
  • のような接続は2回も提供されません.また、順序が変更されると、同じ接続とみなされます.つまり、0と1の間に接続が確立されている場合、1と0は必要ありません.
  • すべての島間の橋梁建設費用は支払われません.この場合,二つの島の間に建設することは不可能であると考えられる.
  • に接続できない島を与えない.

    • I/O例


    ncostsreturn4[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]4

    に答える


    この問題はMST(最小費用ツリー)問題であり,クルーズアルゴリズムで解くことができる.
    import java.util.PriorityQueue;

class Solution {
    int[] parent;
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        PriorityQueue<Pair> queue = new PriorityQueue<>();
        parent = new int[n];
        for(int i=0; i<n; i++)
            parent[i] = i;
        
        for(int i=0; i<costs.length; i++) {
            int start = costs[i][0];
            int end = costs[i][1];
            int cost = costs[i][2];
            
            queue.add(new Pair(start, end, cost));
        }
        
        while(!queue.isEmpty()) {
            Pair temp = queue.poll();
            int start = temp.start;
            int end = temp.end;
            
            int a = find(start);
            int b = find(end);
            
            if(a==b) continue;
            
            union(start, end);
            answer += temp.cost;
        }
        
        return answer;
    }
    
    public class Pair implements Comparable<Pair>{
        int start;
        int end;
        int cost;
        
        public Pair(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Pair p) {
            return this.cost > p.cost ? 1 : -1;
        } 
    }
    
    public void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a<b) parent[b] = a;
        else parent[a] = b;
    }
    
    public int find(int a) {
        if(parent[a]==a)
            return a;
        
        return find(parent[a]);
    }
}
    プログラマ-メニューの更新
    sharedの使い方ptrロックの競合を減らす