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;
}

Download