프로그래밍

www.acmicpc.net/problem/1774  

[난이도] Gold4

[유형] MST(Kruskal)

[풀이]

MST를 구하는 문제이다. 이미 연결되어있는 간선들은 무조건 MST에

포함되어야 하므로 미리 union(merge) 연산으로 합쳐준 뒤에 나머지 최적의

간선들을 합쳐준다. 좌표 범위가 크므로 long long을 사용해야 한다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
using ll = long long;
int N,M,uf[1001],cnt;
double ans;
ll x[1001],y[1001];
double dist(int a,int b){
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}

int find(int a){
    if(uf[a]==a) return a;
    return uf[a] = find(uf[a]);
}
bool merge(int a,int b){
    a = find(a);
    b = find(b);
    if(a==b) return 0;
    uf[a] = b;
    return 1;
}
struct edge{
    int u,v;
    double d;
};
vector<edge> egs;
bool cmp(edge& a,edge& b){
    return a.d < b.d;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++){
        scanf("%d%d",&x[i],&y[i]);
        uf[i]=i;
    }
    for(int i=0;i<M;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(merge(u,v)){
            cnt++;
        }
    }    
    for(int i=1;i<N;i++)
        for(int j=i+1;j<=N;j++)
            egs.push_back({i,j,dist(i,j)});
    sort(egs.begin(),egs.end(),cmp);
    for(int i=0;i<egs.size();i++){
        if(merge(egs[i].u,egs[i].v)){
            ++cnt;
            ans+=egs[i].d;
        }
        if(cnt==N-1) break;
    }
    printf("%.2f",ans);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1774.cpp

www.acmicpc.net/problem/6497

[난이도] Gold4

[유형] MST (크루스칼)

[풀이]

Kruskal 알고리즘을 이용하여 MST를 구함 주의할점 1. TC가 여러개일 수도 있다. (입력 0 0을 기준으로 종료) 2. 절약할 수 있는 양을 구해야 하므로 전체 - MST값을 빼준다.Kruskal 알고리즘을 이용하여 MST를 구함
주의할점
1. TC가 여러개일 수도 있다. (입력 0 0을 기준으로 종료)
2. 절약할 수 있는 양을 구해야 하므로 전체 - MST값을 빼준다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int mx = 2e5;
int N,M,uf[mx];
struct P{
    int a,b,c;
};
vector<P> v;
bool cmp(P& a,P& b){
    return a.c < b.c;
}
int find(int a){
    if(a==uf[a]) return a;
    return uf[a] = find(uf[a]);
}
bool merge(int a,int b){
    a = find(a);
    b = find(b);
    if(a==b) return 0;
    uf[a] = b;
    return 1;
}

int main(){
    while(1){
        int t=0;
        v.clear();
        scanf("%d%d",&N,&M);
        if(N==0&&M==0) return 0;
        for(int i=0;i<M;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            t+=c;
            v.push_back({a,b,c});
        }
        sort(v.begin(),v.end(),cmp);
        for(int i=0;i<N;i++) uf[i]=i;
        int ans =0,cnt=0;
        for(int i=0;i<v.size();i++){
            if(merge(v[i].a,v[i].b)){
                ans+=v[i].c;
                if(++cnt==N-1) break;
            }
        }
        printf("%d\n",t-ans);
    }
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/6497.cpp

www.acmicpc.net/problem/4386

[난이도] Gold4

[유형] MST (크루스칼)

[풀이]

모든 좌표들간의 거기를 계산하여 저장 한 뒤 크루스칼 알고리즘을 이용하여 MST를 구하면 된다.

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
struct eg{
    int a,b;
    double cost;
};
vector<eg> v;
int N,uf[100];
double x[100],y[100];

bool cmp(eg& a,eg& b){
    return a.cost < b.cost;
}

int find(int a){
    if(a==uf[a]) return a;
    return uf[a] = find(uf[a]);
}

bool merge(int a,int b){
    a = find(a);
    b = find(b);
    if(a==b) return 0;
    uf[a] = b;
    return 1;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%lf%lf",&x[i],&y[i]);
    for(int i=0;i<N-1;i++){
        for(int j=i+1;j<N;j++){
            double dist = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
            v.push_back({i,j,dist});
        }
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=0;i<N;i++) uf[i] = i;
    int cnt = 0;
    double ans = 0;
    for(int i=0;;i++){
        if(merge(v[i].a,v[i].b)){
            ans+=v[i].cost;
            if(++cnt==N-1) break;
        }
    }
    printf("%f",ans);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/4386.cpp

www.acmicpc.net/problem/1647

[난이도] Gold4

[유형] 최소 스패닝 트리 (크루스칼)

[풀이]

크루스칼 알고리즘을 이용해 MST를 구하고 그중 가장 큰 edge를 제거하면 cost를 가장 작게하면서 마을을 두개로 나눌 수 있다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct eg{
    int c,a,b;
};
vector<eg> v;
int N,M,uf[100001],cnt,ans;
bool cmp(eg& a,eg& b){
    return a.c < b.c;
}
int find(int a){
    if(a==uf[a]) return a;
    return uf[a] = find(uf[a]);
}
bool merge(int a,int b){
    int pa = find(a);
    int pb = find(b);
    if(pa==pb) return 0;
    uf[pa] = find(pb);
    return 1;
}
int main(){
    scanf("%d%d",&N,&M);
    v.resize(M);
    for(int i=0;i<M;i++){
        scanf("%d%d%d",&v[i].a,&v[i].b,&v[i].c);
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=1;i<=N;i++) uf[i] = i;
    for(int i=0;;i++){
        if(merge(v[i].a,v[i].b)){
            if(++cnt==N-1) break;
            ans+=v[i].c;
        }
    }
    printf("%d",ans);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1647.cpp

www.acmicpc.net/problem/1199

[난이도] Gold4

[유형] 최소 스패닝 트리 (크루스칼)

[풀이] 크루스칼 알고리즘

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct edge{
    int a,b,cost;
};
int V,E,uf[10001];
vector<edge> eg;
bool cmp(edge& a,edge& b){
    return a.cost < b.cost;
}

int find(int a){
    if(uf[a]==a) return a;
    return uf[a] = find(uf[a]);
}

bool merge(int a,int b){
    int pa = find(a);
    int pb = find(b);
    if(pa==pb) return 0;
    uf[pa] = pb;
    return 1;
}
int main(){
    scanf("%d%d",&V,&E);
    for(int i=0;i<E;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        eg.push_back({a,b,c});
    }
    sort(eg.begin(),eg.end(),cmp);
    for(int i=1;i<=V;i++) uf[i] = i;
    int cnt = 0, ans = 0;
    for(int i=0;;i++){
        edge e = eg[i];
        if(merge(e.a,e.b)){
            ans+=e.cost;
            if(++cnt==V-1) break;
        }
    }
    printf("%d",ans);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1199.cpp