变形的模板题
只要建图建得好,瞬间变模板题
我们设 n+1 为超级发电站,连接其他所有点,边权就是这个点建立发电站的代价
然后跑一个裸的最小生成树,就轻松A掉了
#include<bits/stdc++.h>
using namespace std;
int fa[305];
int n;
int x;
struct oppo{
int from,to,s;
}rood[100000];
int tot;
bool rule(oppo a,oppo b)
{
return a.s<b.s;
}
int find(int x)//并查集
{
return fa[x]==x?x:fa[x]=find(fa[x]);//返回和路径压缩
}
int ans;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
rood[++tot].from=n+1;
rood[tot].to=i;
rood[tot].s=x;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&x);
if(i>j)
{
rood[++tot].from=i;
rood[tot].to=j;
rood[tot].s=x;
}
}
sort(rood+1,rood+tot+1,rule);
for(int i=1;i<=n+1;i++)
fa[i]=i;
for(int i=1;i<=tot;i++)
{
int a=find(rood[i].from);
int b=find(rood[i].to);
if(a!=b)
{
fa[a]=b;
ans+=rood[i].s;
}
}
cout<<ans<<endl;
return 0;
}