HDUOJ 5253 连接的管道

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5253

题意:略。

思路:本质是求最小生成树,点与点之间的边权是两个点的权值之差的绝对值。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1000+5;
struct Edge{
    int u,v,w;
    Edge(int _,int __,int ___):u(_),v(__),w(___){}
};
int n,m,T;
int a[maxn][maxn];
int fa[maxn*maxn];
int dir_x[2]={0,-1};
int dir_y[2]={-1,0};
vector<Edge>edges;
int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
bool cmp(const Edge&a,const Edge&b){return a.w<b.w;}
int main(){
    scanf("%d",&T);
    for (int cas=1;cas<=T;cas++){
        scanf("%d%d",&n,&m);
        int cnt=0;
        for (int i=1;i<=n;i++){
            for (int j=1;j<=m;j++){
                scanf("%d",&a[i][j]);
                cnt=m*(i-1)+j;
                fa[cnt]=cnt;
            }
        }
        for (int i=1;i<=n;i++){
            for (int j=1;j<=m;j++){
                for (int k=0;k<2;k++){
                    int tx=i+dir_x[k];
                    int ty=j+dir_y[k];
                    if (tx<=0 || tx>n || ty<=0 || ty>m) continue;
                    edges.push_back(Edge(m*(i-1)+j,m*(tx-1)+ty,abs(a[i][j]-a[tx][ty])));
                }
            }
        }
        sort(edges.begin(),edges.end(),cmp);
        int c=0,sum=0;
        cnt=n*m;
        for (int i=0;i<(int)edges.size();i++){
            int u=edges[i].u,v=edges[i].v;
            int tx=Find(u),ty=Find(v);
            if (tx!=ty){
                sum+=edges[i].w;
                fa[tx]=ty;
                if (++c>=cnt-1) break;
            }
        }
        printf("Case #%d:\n",cas);
        printf("%d\n",sum);
        edges.clear();
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注