[APC001] D Forest

Description

给定\(n\)个点\(m\)条边组成的森林，每个点有权值\(a_i\)。现在需要将森林连成一棵树，选择两个点\(i,j\)连边的代价是\(a_i+a_j\)，每个点最多被选择连边一次。问最小代价。

Solution

首先dfs找出图里联通块个数记为\(x\)。

因为要连成一棵树，所以要连\(x-1\)条边，所以要选择\(2x-2\)个点。

我们不是很需要关心最后连接成的树的形态。贪心的选出代价最小的\(2x-2\)个点就好。

现在每个联通块内选出\(1\)个权值最小的点，这样保证了每个联通块都有点和其他联通块相连。

然后剩下的\(x-2\)个点随便选，选择没有被选过且\(a\)最小的点就好了。

Code

#include<set>

#include<map>

#include<cmath>

#include<queue>

#include<cctype>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using std::min;

using std::max;

using std::swap;

using std::vector;

const int N=1e5+5;

typedef double db;

typedef long long ll;

#define pb(A) push_back(A)

#define pii std::pair<ll,int>

#define mp(A,B) std::make_pair(A,B)

pii val[N];

int n,m,used[N];

int cnt,head[N],vis[N];

struct Edge{

    int to,nxt;

}edge[N<<1];

void add(int x,int y){

    edge[++cnt].to=y;

    edge[cnt].nxt=head[x];

    head[x]=cnt;

}

ll getint(){

    ll X=0,w=0;char ch=0;

    while(!isdigit(ch))w|=ch=='-',ch=getchar();

    while( isdigit(ch))X=X*10+ch-48,ch=getchar();

    if(w) return -X;return X;

}

std::priority_queue< pii > pq[N];

void dfs(int now,int tot){

    vis[now]=tot;

    pq[tot].push(mp(-val[now].first,now));

    for(int i=head[now];i;i=edge[i].nxt){

        int to=edge[i].to;

        if(vis[to]) continue;

        dfs(to,tot);

    }

}

signed main(){

    n=getint(),m=getint();

    for(int i=1;i<=n;i++) val[i].first=getint(),val[i].second=i;

    for(int i=1;i<=m;i++){

        int x=getint()+1,y=getint()+1;

        add(x,y);add(y,x);

    } int tot=0;

    for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,++tot);

    if(tot==1) return printf("0"),0;

    if(2*tot-2>n) return printf("Impossible"),0;

    ll ans=0;

    for(int i=1;i<=tot;i++){

        ans+=-pq[i].top().first;

        used[pq[i].top().second]=1;

    } std::sort(val+1,val+1+n);

    int cnts=0;

    for(int i=1;i<=n;i++){

        if(cnts==tot-2) break;

        while(i<=n and used[val[i].second]) i++;

        ans+=val[i].first;cnts++;

    } printf("%lld\n",ans);

    return 0;

}

巴特西

[APC001] D Forest

Description

Solution

Code

最新文章

热门文章