题解 P1195 【口袋的天空】

Floating__Dream · 2018-08-02 10:11:51 · 题解

连接一条边----连通块数量减一 k个连通块-----连（n-k）边 运用kruskal算法的思想：每次连可以连的边中代价最小的 （贪心） 使用 并查集维护

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
int n,k,m;
int fa[1000050];
struct node {
    int x;
    int y;
    int l;
} a[1000005];
int cmp( const void *a , const void *b ) {
    struct node *c = (node *)a;
    struct node *d = (node *)b;
    return c->l - d->l;
}
int find(int x)
{
    if(x!=fa[x])
    fa[x]=find(fa[x]);
    return fa[x];
}
void work(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)
    return;
    fa[x]=y;
}
int main() {
    cin>>n>>m>>k;
    for(int i=0; i<m; i++) {
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].l);
    }
    qsort(a,m,sizeof(a[0]),cmp);
    for(int i=1;i<=n;i++)
    fa[i]=i;
    int num=n-k;
    int ans=0;
    for(int i=0;i<m;i++)
    {
        if(num==0)
        break;
        int aaa=find(a[i].x);
        int wzx=find(a[i].y);
        if(aaa!=wzx)
        {
            work(a[i].x,a[i].y);
            ans+=a[i].l;
            num--;
        }
    }
    if(num)
    cout<<"No Answer"<<endl;
    else
    cout<<ans<<endl;
}