题意：在一个无向图中，给你几个源点，找出把所有点连接到源点后最小的消费；
可以利用并查集：
先用结构体把每个边存起来，再按照消费大小排序。之后从消费小的到大的一个个尝试，两个点需要连接的话，连接上同时把消费也算上去；
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
const int inf = 0x3f3f3f; using namespace std; int n,k;
int fa[+];
struct node
{
int from,to;
int c;
}a[];
bool cmp(node a,node b)
{
return a.c<b.c;
}
void init(){
for(int i=;i<=n;i++)
fa[i] = i;
}
int find(int x)
{
if(fa[x]==x)return x;
else return fa[x] = find(fa[x]);
}
int uni(int x,int y)
{
if(fa[x]==-&&fa[y]==-)return ; //（**）
int px = find(x);
int py = find(y);
if(px==py)return ;
else
{
fa[px] = py;
return ;
}
} int main(){
scanf("%d%d",&n,&k);
init();
for(int i=;i<=k;i++)
{
int x;
scanf("%d",&x);
fa[x]=-; //这个操作我其实不是很明确，我以我的理解加上了（**）这句，
} //表示源点之间不用连接，但是别人写的好像不用加这句话。
int cnt =;
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
int cost;
scanf("%d",&cost);
if(cost==)continue;
a[++cnt].c=cost;
a[cnt].from = i;
a[cnt].to =j;
}
}
sort(a+,a++cnt,cmp);
int ans = ;
for(int i=;i<=cnt;i++)
{
if(uni(a[i].from,a[i].to))
{
ans += a[i].c;
}
}
printf("%d\n",ans);
return ;
}
我自己就做了一个预处理，（直接把读入的用uni连接起来
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
const int inf = 0x3f3f3f; using namespace std; int n,k;
int fa[+];
struct node
{
int from,to;
int c;
}a[];
bool cmp(node a,node b)
{
return a.c<b.c;
}
void init(){
for(int i=;i<=n;i++)
fa[i] = i;
}
int find(int x)
{
if(fa[x]==x)return x;
else return fa[x] = find(fa[x]);
}
int uni(int x,int y)
{
int px = find(x);
int py = find(y);
if(px==py)return ;
else
{
fa[px] = py;
return ;
}
} int main(){
scanf("%d%d",&n,&k);
init();
int last=-;
for(int i=;i<=k;i++)
{
int x;
scanf("%d",&x);
if(last!=-)
{
int suibian;
suibian =uni(last,x); //不理解别人把fa[x]=-1的操作；
last = x; //自己就先预处理连接好了；
}
else last=x;
}
int cnt =;
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
int cost;
scanf("%d",&cost);
if(cost==)continue;
a[++cnt].c=cost;
a[cnt].from = i;
a[cnt].to =j;
}
}
sort(a+,a++cnt,cmp);
int ans = ;
for(int i=;i<=cnt;i++)
{
if(uni(a[i].from,a[i].to))
{
ans += a[i].c;
}
}
printf("%d\n",ans);
return ;
}