つなぎ島

質問する

https://programmers.co.kr/learn/courses/30/lessons/42861

コード#コード#

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

bool compare(vector<int> a,vector<int> b){ return a[2]>b[2]; }

bool bfs( vector<vector<int>> graph){
    queue<pair<int,int>> q;
    q.push({0,0});
        
    while(!q.empty()){
        int y=q.front().first;
        int x=q.front().second;
        q.pop();
        
        for(int i=0;i<graph.size();i++){
            if(graph[i][x]==1){
                graph[i][x]=2;
                q.push({i,x});
            }
            if(graph[y][i]==1){
                graph[y][i]=2;
                q.push({y,i});
            }
        } 
    }
    for(int i=0;i<graph.size();i++){
        if(graph[i][i]==1) return false;
    }
    return true;
}
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    vector<vector<int>> graph(n,vector<int>(n,0));
    
    for(int i=0;i<costs.size();i++){
        graph[costs[i][0]][costs[i][1]]=1;
        graph[costs[i][1]][costs[i][0]]=1;
        
        answer+=costs[i][2];
    }
    for(int i=0;i<n;i++){
       graph[i][i]=1; 
    }
    sort(costs.begin(),costs.end(),compare);
    
    for(auto i:costs){
        graph[i[0]][i[1]]=0;
        graph[i[1]][i[0]]=0;
        if(bfs(graph)) answer-=i[2];
        else{
            graph[i[0]][i[1]]=1;
            graph[i[1]][i[0]]=1;
        }       
    }
    return answer;
}

に答える

ネットの問題に似ているように見えます.島の数とこれらの島を接続するコストを教えてくれると、すべての島を接続する最低コストを知る必要があります.
私が確立した論理は、すべての島を接続した後、コストの高い順序で一つ一つ削除し、削除しても島を接続した場合、削除し、接続できなければ、元の状態に戻る方法で値を求めることです.
コードでは、まずすべての幹線をグラフィックに接続し、次にコストを追加します.
コスト降順に幹線を並べ、bfsを使用してすべての島が接続されているかどうかを判断します.