首页 > 代码库 > 最小生成树

最小生成树

1.

技术分享
/*dfs+kruskaldfs:联通块染色+建图(横坐标一条边纵坐标一条边) 最后kruskal思想 把所有联通快联通统计边数和最小边权和即可 */#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define N 60using namespace std;char a[N][N];int map[N][N],fa[360100];int n,m,cnt,cnt2,k,sum;int dx[9]={0,0,0,1,-1,1,1,-1,-1};int dy[9]={0,1,-1,0,0,1,-1,1,-1};struct node{    int u,to,dis;}t[360100];inline bool cmp(const node&a,const node &b){    return a.dis<b.dis;}inline void add(int u,int to,int dis){    t[++cnt2].u=u;t[cnt2].to=to;t[cnt2].dis=dis;}void dfs(int x,int y)//联通块染色 {    map[x][y]=cnt;    for(int i=1;i<=8;i++)    {        int tx=x+dx[i],ty=y+dy[i];        if(a[tx][ty]==#)        {            a[tx][ty]=.;            dfs(tx,ty);        }    }}void find(int x,int y){    for(int i=1;i<=m;i++)//纵坐标连边     {        if(y+i>m) break;        if(map[x][y]==map[x][y+1]) break;        for(int j=1;j<=8;j++)        {            int tx=x+dx[j],ty=y+i+dy[j];            if(map[tx][ty]!=0 && map[tx][ty]!=map[x][y])              add(map[x][y],map[tx][ty],i);        }    }    for(int i=1;i<=n;i++)//横坐标连边     {        if(x+i>n) break;        if(map[x+1][y]==map[x][y]) break;        for(int j=1;j<=8;j++)        {            int tx=x+i+dx[j],ty=y+dy[j];            if(map[tx][ty]!=0 && map[tx][ty]!=map[x][y])              add(map[x][y],map[tx][ty],i);        }    }}inline int find(int x){    if(fa[x]==x) return x;    else return x=find(fa[x]);}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n*m;i++) fa[i]=i;    for(int i=1;i<=n;i++)      for(int j=1;j<=m;j++)        cin>>a[i][j];    for(int i=1;i<=n;i++)      for(int j=1;j<=m;j++)      {            if(a[i][j]==#)            {                 a[i][j]=.; ++cnt;                 dfs(i,j);          }      }    for(int i=1;i<=n;i++)      for(int j=1;j<=m;j++)      {          if(map[i][j]) find(i,j);      }    sort(t+1,t+cnt2+1,cmp);    for(int i=1;i<=cnt2;++i)    {        int sa=find(t[i].u),sb=find(t[i].to);        if(sa!=sb)        {            fa[sb]=sa;++k;            sum+=t[i].dis;        }    }    printf("%d\n",cnt);    printf("%d %d\n",k,sum);    return 0;    return 0;    return 0;}
codevs1002

 

最小生成树