引水工程
时间限制：2000 ms | 内存限制：65535 KB
难度：3
-> Link <- 5月份省赛集训的时候这道题还不是很拿手，不过今天又看了看才发现水的一笔；
题意：有n个区域（n<=300）;每个区域可以自建水库，有一定的费用，也可以修建渠道连接其他的区域引水，问要使得整个区域都能用水，工程最小费用是多少；
思路：典型的最小生成树，只不过可以有某个区域自建水库，那么我们就可以再建一个点，就建0点吧，假设0区域就是一个水库，修建渠道给个区域的费用已知，不就是求整个区域的最下生成树；博主用的是ks算法，其中存图时要记得数组开大一点，每个区域两两都可以联通，可能的渠道就有90000条，博主就是在这里跪了几遍；
#include<bits/stdc++.h>
using namespace std;
const int N=90000+10;
struct node
{int u,v,w;
} a[N];
int n,k,f[N];
int cmp(node a,node b)
{return a.w<b.w;
}
int find(int x)
{return f[x]==-1?x:f[x]=find(f[x]);
}
void ks(int n)//裸kustral算法；
{int x=0,i;long long sum=0;memset(f,-1,sizeof(f));sort(a,a+k,cmp);for(i=0; i<k; i++){int u=find(a[i].u);int v=find(a[i].v);if(u!=v){f[u]=v;sum+=a[i].w;x++;}if(x>=n) break;//注意这个；}printf("%lld\n",sum);
}
int main()
{int t,i,j,w;scanf("%d",&t);while(t--){memset(a,0,sizeof(a));scanf("%d",&n);k=0;for(i=1; i<=n; i++){scanf("%d",&w);a[k].u=0,a[k].v=i,a[k++].w=w;//建立0点；}for(i=1; i<=n; i++)for(j=1; j<=n; j++){scanf("%d",&w);if(j>i)a[k].u=i,a[k].v=j,a[k++].w=w;//存图；}ks(n);}return 0;
}