프로그래밍

https://www.acmicpc.net/problem/2406

[난이도] Gold3
[유형] MST

[풀이]
1번 컴퓨터가 아닌 다른 컴퓨터가 고장나거나, 다른 컴퓨터끼리의 연결이 끊어져도 어차피
1번 컴퓨터와 모든 컴퓨터가 연결되어 있기 때문에 안정적인 네트워크가 유지됩니다.
즉, 1번 컴퓨터가 고장난 경우만 고려하면 되므로,
1번 컴퓨터가 없을 때 나머지 컴퓨터들이 최소 스패닝 트리 (MST)를 이루도록 간선을 연결해주면 됩니다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,M,uf[1001],adj[1001][1001];
struct P{
    int u,v,d;
};
int find(int n){
    if(n==uf[n]) return n;
    return find(uf[n]);
}
bool merge(int u,int v){
    u=find(u);
    v=find(v);
    if(u==v) return 0;
    uf[u] = v;
    return 1; 
}
bool cmp(P& a,P& b){
    return a.d < b.d;
}
bool check(){
    int r = find(2);
    for(int i=2;i<=N;i++){
        if(find(i)!=r) return 0;
    }
    return 1;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) uf[i]=i;
    while(M--){
        int a,b;
        scanf("%d%d",&a,&b);
        adj[b][a]=adj[a][b]=1;
        merge(b,a);
    }
    vector<P> edges;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            int v;
            scanf("%d",&v);
            if(i==1||j==1||i>=j||adj[i][j]) {
                continue;
            }
            if(find(i)!=find(j)) {
                edges.push_back({i,j,v});
            }
        }
    }
    sort(edges.begin(),edges.end(),cmp);
    vector<pair<int,int>> ret;
    int sum=0;
    for(auto [u,v,d] : edges){
        if(merge(u,v)){
            ret.push_back({u,v});
            sum+=d;
            if(check()) break;
        }
    }
    printf("%d %d\n",sum,ret.size());
    for(auto [u,v] : ret){
        printf("%d %d\n",u,v);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/2406.cpp

https://www.acmicpc.net/problem/1414

[난이도] Gold3
[유형] MST

[풀이]
최소스패닝트리 크루스칼 알고리즘을 이용하여 답을 구할 수 있습니다.

#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cstring>
#include <vector>
using namespace std;
struct P{
    int u,v,d;
};
int N,uf[51],total;
vector<P> a;
bool cmp(P& l ,P& r){
    return l.d < r.d;
}
int find(int n){
    if(uf[n]==n) return n;
    return uf[n] = find(uf[n]);
}
bool merge(int u,int v){
    u = find(u);
    v = find(v);
    if(u==v) return 0;
    uf[u] = v;
    return 1; 
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int d=1;
            char c;
            scanf(" %c",&c);
            if(c=='0') continue;
            if(islower(c)) {
                d+=c-'a';
            }else{
                d+=26;
                d+=c-'A';
            }
            total+=d;
            if(i==j) continue;
            a.push_back({i,j,d});
        }
    }
    memset(uf,-1,sizeof(uf));
    for(int i=0;i<N;i++) uf[i]=i;
    sort(a.begin(),a.end(),cmp);
    int cnt=0,sum=0;
    for(int i=0;i<a.size();i++){
        auto [u,v,d] = a[i];
        if(merge(u,v)){
            sum+=d;
            if(++cnt==N-1) break;
        }
    }
    if(cnt<N-1) {
        puts("-1");
        return 0;
    }
    printf("%d",total-sum);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/1414.cpp

https://www.acmicpc.net/problem/14950

[난이도] Gold3
[유형] MST

[풀이]
최소 스패닝 트리를 구성해주면 됩니다.

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
struct P{ int u,v,d; };
int N,M,t,uf[10001];
vector<P> a;
bool cmp(P& l,P& r){ return l.d < r.d; }
int find(int n){
    if(n==uf[n]) return n;
    return find(uf[n]);
}
bool merge(int u,int v){
    u=find(u);
    v=find(v);
    if(u==v) return 0;
    uf[u]=v;
    return 1;
} 
int main(){
    scanf("%d%d%d",&N,&M,&t);
    while(M--){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        a.push_back({u,v,d});
    }
    sort(a.begin(),a.end(),cmp);
    for(int i=1;i<=N;i++) uf[i]=i;
    int ans=0,ct=0,j=0;
    for(int i=0;i<a.size();i++){
        auto [u,v,d] = a[i];
        if(merge(u,v)){
            ans+=d+ct;
            ct+=t;
            if(++j==N-1) break;
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/14950.cpp

https://www.acmicpc.net/problem/10423

[난이도] Gold2
[유형] MST

[풀이]
발전소를 같은 그룹으로 취급하고 크루스칼 알고리즘을 돌려주면 쉽게 정답을 구할 수 있다.

처음에 위 방법이 생각이 나지 않아서 프림 알고리즘으로 MST를 구현하였다.

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
int N,M,K;
vector<pair<int,int>> adj[1001];
vector<int> p;
bool visit[1001];
int main(){
    scanf("%d%d%d",&N,&M,&K);
    for(int i=0;i<K;i++){
        int v;
        scanf("%d",&v);
        p.push_back(v);
    }
    for(int i=0;i<M;i++){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    for(auto a : p) {
        for(auto e : adj[a]){
            pq.push({e.second,e.first});
        }
        visit[a]=1;
    }
    int ans = 0,cnt=p.size();
    while(!pq.empty()){
        auto qt = pq.top(); pq.pop();
        int cur = qt.second;
        if(visit[cur]) continue;
        visit[cur]=1;
        ans+=qt.first;
        if(++cnt==N) break;
        for(auto e : adj[cur]){
            int nxt=e.first;
            int w=e.second;
            pq.push({w,nxt});
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/10423.cpp

https://www.acmicpc.net/problem/14621

[난이도] Gold3
[유형] MST

[풀이]
u,v의 성별이 같은 edge는 버리고 크루스칼 알고리즘을 이용해 MST를 구해주면 된다.

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/14621.cpp

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,M,uf[1001];
bool check[1001];
struct P{
    int u,v,d;
};
vector<P> vec;
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%d",&N,&M);
    for(int i=1;i<=N;i++) {
        char a;
        scanf(" %c",&a);
        check[i]=a=='M';
    }
    while(M--){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        if(check[u]!=check[v]) vec.push_back({u,v,d});
    }
    sort(vec.begin(),vec.end(),[](P& a,P& b)->bool{
        return a.d<b.d;
    });
    for(int i=1;i<=N;i++) uf[i]=i;

    int ans=0,cnt=0;
    for(int i=0;i<vec.size();i++){
        if(merge(vec[i].u,vec[i].v)){
            ans+=vec[i].d;
            if(++cnt==N-1){
                printf("%d",ans);
                return 0;
            }
        }
    }
    puts("-1");
}

https://www.acmicpc.net/problem/13418

[난이도] Gold3
[유형] MST

[풀이]
피로도가 최소가 되게 할려면 edge cost가 1(내리막)인 edge를 우선으로 선택하게 해야하므로
오름차순으로 정렬, 최대가 되게 할려면 0(오르막)인 edge를 우선으로 선택하게 해야하므로
내림차순으로 정렬 뒤 Kruskal 알고리즘으로 MST를 구해주면 된다. 이 때, 총 가중치의 값은
필요 없고 선택된 edge중에 0(오르막)인 edge의 개수를 구해서 제곱해주면 최소,최대일때의
피로도를 각각 구할 수 있다.

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/13418.cpp

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,M,uf[1001];
struct P{int a,b,c;};
vector<P> v;
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;
}

int ksk(){
    for(int i=0;i<=N;i++) uf[i]=i;

    int cnt=0,ret=0;
    for(int i=0;i<v.size();i++){
        if(merge(v[i].a,v[i].b)){
            if(v[i].c==0) ret++;
            if(++cnt==N) break;
        }
    }
    return ret*ret;
}

int main(){
    scanf("%d%d",&N,&M);
    M++;
    while(M--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        v.push_back({a,b,c});
    }
    sort(v.begin(),v.end(),[](P& u,P& v)->bool{
        return u.c<v.c;
    });
    int ans = ksk();

    sort(v.begin(),v.end(),[](P& u,P& v)->bool{
        return u.c>v.c;
    });
    ans -= ksk();
    printf("%d",ans);
}

https://www.acmicpc.net/problem/16398

[난이도] Gold4
[유형] MST

[풀이]
Kruskal 알고리즘

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/16398.cpp

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct P{
    int a,b,c;
};
int N,uf[1001];
vector<P> vec;
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++){
        for(int j=0;j<N;j++){
            int v;
            scanf("%d",&v);
            if(i<j) vec.push_back({i,j,v});
        }
    }
    sort(vec.begin(),vec.end(),[](P& u,P& v)->bool{
        return u.c<v.c;
    });
    for(int i=0;i<N;i++) uf[i]=i;
    int cnt=0;
    long long ans=0;
    for(int i=0;i<vec.size();i++){
        auto k = vec[i];
        if(merge(k.a,k.b)){
            ans+=k.c;
            if(++cnt==N-1) break;
        }
    }
    printf("%lld",ans);
}

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