[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;
}
上一篇:poj 3048 Max Factor(素数筛)


下一篇:JS代码判断IE6,IE7,IE8,IE9的函数代码