首页 > 代码库 > 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枚举组合情况+最小生成树