oj.uz

답안 #725461

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
725461 2023-04-17T13:24:41 Z vjudge1 Kronican (COCI16_kronican) C++17
70 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>
using namespace std;

const int MN=21;

int n,k;
int board[MN][MN];
int par[MN];
bool check[MN];

struct mst{
    int left;
    int right;
    int weight;
}temp;

bool operator < (mst x,mst y){
    return x.weight>y.weight;
}

void build(){
    for(int i=1;i<=n;++i){
        par[i]=-1;
    }
}

int find(int u){
    if(par[u]<0) return u;
    return par[u]=find(par[u]);
}

void unionn(int a,int b){
    a=find(a);
    b=find(b);

    if(a==b) return;
    par[a]+=par[b];
    par[b]=a;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    priority_queue<mst> pq;
    cin>>n>>k;
    build();
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cin>>board[i][j];
            if(i!=j){
                temp.left=i;
                temp.right=j;
                temp.weight=board[i][j];
                pq.push(temp);
            }
        }
    }

    int cnt=n-k,ans=0;

    while(cnt>0){
        temp=pq.top();
        pq.pop();

        int l=temp.left,r=temp.right;
        
        if(find(l)==find(r)) continue;
        if(check[l]) continue;
        check[l]=true;
        check[r]=false;
        
        unionn(l,r);
        ans+=temp.weight;
        --cnt;
    }

    cout<<ans;
}

Subtask #1
70.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Correct 1 ms 212 KB Output is correct