原图可能有多个连通分量，先DFS找出每个连通分量中最小节点，这些必然是要攻占的城市。
设 n 为节点数， m 为边数， cnt 为初始连通分量数，在剩下的边数不小于 m - (n - cnt) 的时候，图的连通性是不变的，也就是在这之前可以适当策略删边保持结果不变。
当边数小于等于 m - (n - cnt) 时，每删一条边，必然多一个连通分量，我们总可以做到让多出来这个连通分量的最小结点 是所有节点中除去已经选定的那些节点之外的最小节点，所以这时对节点以权值排序从小往大记到删够边数为止。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
typedef long long LL;
const int maxn = ;
const int maxm = ;
int n, m, k;
int fst[maxn];
int wt[maxn];
int vis[maxn];
int nex[maxm], w[maxm], ntp;
void AddEdge(int a, int b)
{
nex[ntp] = fst[a];
w[ntp] = b;
fst[a] = ntp ++;
}
inline int min(int a, int b){return a < b ? a : b;}
void DFS(int nd, int &okcity)
{
if(vis[nd]) return;
vis[nd] = true;
if(okcity == - || wt[nd] < wt[okcity])
okcity = nd;
for(int i = fst[nd]; i != -; i = nex[i])
DFS(w[i], okcity);
}
int main()
{
int t, ca;
for(scanf("%d", &t), ca = ; ca <= t; ca ++)
{
int a, b;
scanf("%d%d%d", &n, &m, &k);
memset(fst, -, sizeof(fst));
memset(vis, , sizeof(vis));
for(int i = ; i <= n; i ++)
scanf("%d", &wt[i]);
ntp = ;
for(int i = ; i < m; i ++)
{
scanf("%d%d", &a, &b);
AddEdge(a, b);
AddEdge(b, a);
}
int cnt = ;
LL ans = ;
for(int i = ; i <= n; i ++)
{
int okcity = -;
DFS(i, okcity);
if(okcity != -)
cnt ++, ans += wt[okcity], vis[okcity] = ;
} if((k -= m - (n - cnt)) > )
{
int i, j;
for(i = , j = ; i <= n; i ++)
if(vis[i] != ) wt[j ++] = wt[i];
std::sort(wt + , wt + j);
for(int i = ; k > && i <= j; i ++)
ans += wt[i], k --;
}
printf("Case #%d: %lld\n", ca, ans);
}
return ;
}