P1550打井

这是USACO2008年的一道最小生成树题，感谢dzj老师那天教的图论。

要引渠让每一个村庄都可以接到水，然后从某一个村庄到另一个村庄修剪水道要花费w元，并且还要打井（至少一个）(而输入数据也包括了在每一个村庄打井的费用),需要为使所有农场都与有水的村庄相连或拥有水井所需要的钱数。很明显，这个题只有建成一个联通的图，然后求最小权值和即可。所以我选用了kruskal算法求最小生成树。但是这里还有一个问题，就是怎么判断是打井还是连水道的问题。那么我们则用到了“超级元”的思想，让水井代表0号节点，则边权费用，这样就转化为了克鲁斯卡尔算法的模型。

1.注意将实际问题算法模型化

2.如果有不一样的地方，要进行转化，这里常用超级元来解决

3.注意初始化问题，别乱来，建议用memset，不算慢且全

代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define maxn 5000

#define maxm 200000

using namespace std;

int fa[maxn];

struct edge{

    int u,v,w;

}e[maxm];

int n,m;

int u,v;

int ans=;

int tot;

void init(){//初始化

    memset(fa,-,sizeof(fa));

}

int getFa(int x){

    if(fa[x]==-) return x;

    else return fa[x]=getFa(fa[x]);

}

void merge(int x,int y){

    fa[x]=y;

}

bool cmp(edge a,edge b){//结构体比较

    return a.w<b.w;

}

int cnt=;

int main(){

    init();

    cin>>n;

    for(int i=;i<=n;i++){

        int w;

        cin>>w;

        tot++;

        e[tot].u=;

        e[tot].v=i;

        e[tot].w=w;

    }

    for(int i=;i<=n;i++){

        for(int j=;j<=n;j++){

            int w;

            cin>>w;

            tot++;

            e[tot].u=i;

            e[tot].v=j;

            e[tot].w=w;

        }

    }

    sort(e,e+tot+,cmp);//按照权值排序，贪心思想

    for(int i=;i<=tot-;i++){

        int t1=getFa(e[i].u);

        int t2=getFa(e[i].v);

        if(t2!=t1){

            merge(t1,t2);

            ans+=e[i].w;

        }

    }

    cout<<ans;

    return ;

}

巴特西

P1550打井

最新文章

热门文章