首页 > 代码库 > 最小生成树
最小生成树
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;}
最小生成树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。