78.Wonderland(Kruskal MSTアルゴリズム)

1536 ワード
アルゴリズム#アルゴリズム# コーディングテスト テキストリンク

■説明の入力
第1行は、都市の個数V(1≦V≦25)および道路の個数E(1≦E≦200)を与える.
各道路の情報を表す3つの整数A,B,Cが与えられる.これはA番都市とB番都市です.
これは、街のメンテナンス費用がC道路につながっていることを意味します.C値は10万を超えない.
■出力説明
すべての都市を接続するのに必要な最低料金を支えようとします.
■入力例1
[C++創造的に問題を解決]
  • 84 -
    9 12
    1 2 12
    1 9 25
    2 3 10
    2 8 17
    2 9 8
    3 4 18
    3 7 55
    4 5 44
    5 6 60
    5 7 38
    7 8 35
    8 9 15
    ■出力例1
    196
    • #include
    #include
    #include
    #include
    using namespace std;
    int unf[1001];
    struct Edge{
    int s;
    int e;
    int val;
    Edge(int a,int b, int c){
    s=a;
    e=b;
    val=c;
    }
    bool operator<(const Edge &b) const {
    return val}
    };
    int Find(int v){
    if(v==unf[v]) return v;
    else return unf[v]=Find(unf[v]);
    }
    void Union(int a,int b){
    a=Find(a);
    b=Find(b);
    if(a!=b)unf[a]=b;
    }
    int main() {
    vector<Edge> Ed; //Edge라는 구조체 형성 
int i,n,m,a,b,c,cnt=0,res=0;
cin>>n>>m; // 노드 갯수 , 간선 수
for(i=1;i<=n;i++){
	unf[i]=i;
	
} 

for(i=1;i<=m;i++){
	cin>>a>>b>>c;
	Ed.push_back(Edge(a,b,c)); //구조체에 값 넣기 
}
sort(Ed.begin(),Ed.end()); // 정렬하기 
for(i=0;i<m;i++){
	int fa=Find(Ed[i].s);
	int fb=Find(Ed[i].e);
	if(fa!=fb){
		res+=Ed[i].val;
		Union(Ed[i].s,Ed[i].e);
	}
} 
cout<<res;
    }
    Docker で WebpackDevServer を実行する
    翻訳js暗号化解読