题解 CF1095F 【Make It Connected】
starseven
2020-06-05 21:22:43
[我的博客中链接](https://www.cnblogs.com/starseven/p/13052401.html)
[题目链接](https://codeforces.com/problemset/problem/1095/F)
[luogu题目链接](https://www.luogu.com.cn/problem/CF1095F)
$因为自己想了很久都没有想出来，所以记录下来$
题目大意：
给你n个点,每个点有一个权值$a[i]$,已知连接两点的代价为$a[i]+a[j]$,现在还有其他的$m$种连接方法,连接$x,y$的代价为$w$,求出让这个图连通的最小代价.
我们看到了**求出让这个图连通的最小代价.**
那明显就是最小生成树了啊。
但是如果我们常规建边，那么需要$n\times(n-1)+m$的时间复杂度，而数据强度是：
$$ n <= 2\times10^5 $$
所以$n^2$的建边是要炸掉的。
所以我们需要思考一些可以帮助我们优化算法的性质。
1. 无用边
对于那个$n\times(n-1)$的边，我们很明显看得出来是完全图。
那么完全图的最小生成树是怎样的呢？
很显然是点值最小的点连接其他所有的点（~~俗称菊花图~~）
而其他边在增加了m条边后还有没有用？
假设有一条边$<x,y>$是有用的，那么其权值为$val[x]+val[y]$,而我们根据最小生成树的定义可以知道，在最小生成树里，这两个点要么都没有和最小点（我们将其设为minn）有边，要么只有一个点和minn有边（因为如果两个点都右边的话就形成图了）
（默认$val[x]<val[y]$）
当都没有连边时：
我们将$<x,y>$这条边删去，再将minn连向其中一个点，那么最小生成树中全职的变化是：
$$ -val[x]-val[y]+val[minn]+val[x/y] $$
我们可以轻松看出是负数，所以这才是真正的最小生成树。
当有连边时：
和上面一样。
所以我们可以知道剩下的边对于最终的最小生成树都没有贡献。所以我们只需要加入$n-1$个边，于是
$$ n\times(n-1)---->n-1$$
时间和空间复杂度大大降低，于是此题可做。
$$ Show\;my\;code\;!$$
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ri register int
#define Starseven main
#define ll long long
using namespace std;
const int N=2e5+20;
int n,m,fa[N];
ll ans;
struct node{
ll val;
int id;
}num[N];
bool cmp(const node &a,const node &b){
return a.val<b.val;
}
struct nod{
int from,to;
ll cos;
}tr[N<<1];
int cnt;
bool cmd(const nod &a,const nod &b){
return a.cos<b.cos;
}
void Add(int x,int y,ll va){
tr[++cnt].from=x;tr[cnt].to=y;tr[cnt].cos=va;
return ;
}
int Find(int x){
if(fa[x]==x) return x;
else return fa[x]=Find(fa[x]);
}
int Starseven(void){
cin>>n>>m;
for(ri i=1;i<=n;i++) num[i].id=fa[i]=i,cin>>num[i].val;
sort(num+1,num+1+n,cmp);
for(ri i=2;i<=n;i++) Add(num[1].id,num[i].id,num[1].val+num[i].val);
for(ri i=1;i<=m;i++){
int x,y;ll va;
cin>>x>>y>>va;
Add(x,y,va);
}
sort(tr+1,tr+1+cnt,cmd);
int judge=0;
for(ri i=1;i<=cnt;i++){
int fx=Find(tr[i].from),fy=Find(tr[i].to);
if(fx==fy) continue;
fa[fx]=fy;
ans+=tr[i].cos;
judge++;
if(judge==n-1) break;
}
cout<<ans<<endl;
return 0;
}
```
后记：
我最开始的时候想到了要和最小点连边，但是我没有在最后想到最小生成树，而是想到了一个一个m的边加入，然后判断是否能够替换，现在想来我就是在没有Kus的基础上想最小生成树，看来我对于图论的知识点还不够熟悉，所以还要加强学习！