jzoj给水【并查集】【最小生成树】

最小生成树】"/>

jzoj给水【并查集】【最小生成树】

>Description
　　FJ决定给N(1<=N<=300)个草地给水，草地编号为1到N。他可以在该草地处建立一口井，也可以建立管道从别的草地引水进来，在第i块草地处挖一口井需要花费W_i(1<=W_i<=100,000)，连接井i和井j的管道需要花费P_ij(1<=P_ij<=100,000,P_ij=P_ji;P_ii=0)。
计算最少需要花费多少才能保证每个草地都有水。

>Input
第一行，一个整数N
第2到N+1行，第i+1行输入W_i
第N+2到2N+1行，每行N个空格隔开的整数，表示P_ij

>Output
输出最少花费。

>Sample Input
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

>Sample Output
9

>解题思路
一开始做的时候想到了是最小生成树，但是本人水到爆炸，忘记最小生成树怎么写了。
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
我写的最小生成树模板题

根据输入的矩阵构建成一个图。另外再加上一个点（我写的是0），把其他所有点都连向0节点，每条边的权值为每个点挖一口井需要花费的价值。然后在最小生成树即可（cyz大佬：你懂的）

>代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct ooo
{int a,b,c;
}a[9000000];
int n,w[305],p[305][305],t,minn,sb,ans,c[305];
bool lhq[305];
bool lil(ooo aa,ooo bb){return aa.c<bb.c;}
int find(int s)
{if(c[s]==s) return s;return c[s]=find(c[s]);
}
int main()
{
//	freopen("water.in","r",stdin);
//	freopen("water.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&w[i]);a[++t].a=i,a[t].b=0,a[t].c=w[i]; //记录边:i连0}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&p[i][j]);for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)a[++t].a=i,a[t].b=j,a[t].c=p[i][j]; //记录边：i连jfor(int i=0;i<=n;i++)c[i]=i;sort(a+1,a+1+t,lil); //排个序for(int i=1;i<=t;i++){int li=find(a[i].a),sa=find(a[i].b);if(li!=sa){ans+=a[i].c; //累加答案if(li<sa) c[sa]=li;else c[li]=sa;}}printf("%d",ans);return 0;
}