首页 > 代码库 > hdu 2489 dfs枚举组合情况+最小生成树
hdu 2489 dfs枚举组合情况+最小生成树
大家都说,搜索是算法的基础。今天最这题就有体会了。在n个顶点里选择m个顶点,求最小生成树。用到了深搜的回溯。所有情况都能枚举。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=20,INF=0x3f3f3f3f;int dist[N],Map[N][N],pre[N];//向外延伸的最短边长,记录图信息,记录连接信息bool p[N];//1表示点已经在树的,0表示点在树外bool f[N][N];int Prim(int n){ int i,j,k,Min,ans=0; for(i=2;i<=n;i++) { p[i]=0; dist[i]=Map[1][i]; pre[i]=1; } dist[1]=0; p[1]=1; for(i=1;i<n;i++) { Min=INF; k=0; for(j=1;j<=n;j++) { if(!p[j]&&dist[j]<Min) { Min=dist[j]; k=j; } } if(k==0) return -1;//G不连通 p[k]=1; ans+=Min; for(j=1;j<=n;j++) { if(!p[j]&&Map[k][j]!=INF&&dist[j]>Map[k][j]) { dist[j]=Map[k][j]; pre[j]=k; } } } return ans;}int nd[N],mat[N][N],cs[N],vb[N];bool vis[N];int num, node, edge;void dfs(int x, int m,int n){ int i,j,k; if(num==m) { int s=0; for(i=1;i<=m;i++) s+=nd[cs[i]]; for(i=1;i<=m;i++) for(j=1;j<=m;j++) Map[i][j]=mat[cs[i]][cs[j]]; int ans=Prim(m); if(ans==-1) return ; if(ans*node < s*edge)//两个分式的比较,变为乘积比较 { node =s; edge=ans; for(i=1;i<=m;i++) vb[i]=cs[i]; } return ; } for(i=x+1;i<=n;i++) { if(!vis[i]) { num++; vis[i]=1; cs[num]=i; dfs(i,m,n); vis[i]=0; --num; } }}void init(){ for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) mat[i][j]=INF;}int main(){ //freopen("test.txt","r",stdin); int n,m,i,j,k; while(scanf("%d%d",&n,&m)!=EOF) { if(!n) break; init(); for(i=1;i<=n;i++) scanf("%d",&nd[i]); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&mat[i][j]); node=1; edge=1000000; for(i=1;i<=n-m+1;i++) { memset(vis,0,sizeof(vis)); vis[i]=1; num=1; cs[num]=i; dfs(i,m,n); } for(i=1;i<m;i++) printf("%d ",vb[i]); printf("%d\n",vb[i]); } return 0;}
hdu 2489 dfs枚举组合情况+最小生成树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。