FWATER - Tưới nước đồng cỏ
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<vector>
#include<algorithm>
#define MAX 333
using namespace std;
struct edge {
int u,v,w;
edge(){}
edge(int _u,int _v,int _w) {
u=_u;v=_v;w=_w;
}
bool operator < (const edge &x) const {
if (w<x.w) return (true);
if (w>x.w) return (false);
return (u+v<x.u+x.v);
}
};
vector<edge> e;
int n;
int up[MAX];
void loadgraph(void) {
scanf("%d",&n);
int i,j,v;
for (i=1;i<=n;i=i+1) {
scanf("%d",&v);
e.push_back(edge(0,i,v));
e.push_back(edge(i,0,v));
}
for (i=1;i<=n;i=i+1)
for (j=1;j<=n;j=j+1) {
scanf("%d",&v);
if (i!=j) e.push_back(edge(i,j,v));
}
for (i=0;i<=n;i=i+1) up[i]=-1;
sort(e.begin(),e.end());
}
int find(int x) {
if (up[x]<0) return (x);
up[x]=find(up[x]);
return (up[x]);
}
void join(int a,int b) {
int x=find(a);
int y=find(b);
if (x==y) return;
up[y]=x;
}
void kruskal(void) {
int i;
int c=0;
int s=0;
for (i=0;i<e.size();i=i+1) {
if (find(e[i].u)!=find(e[i].v)) {
join(e[i].u,e[i].v);
s=s+e[i].w;
c=c+1;
if (c==n) {
printf("%d",s);
return;
}
}
}
}
int main(void) {
//freopen("tmp.inp","r",stdin);
loadgraph();
kruskal();
return 0;
}