首页 > 代码库 > hdu 2489 Minimal Ratio Tree 枚举+最小生成树

hdu 2489 Minimal Ratio Tree 枚举+最小生成树

点的总数很小,直接枚举就好。

#include <stdio.h>#include <string.h>#define N 20#define inf 1000000int mk[N],n,k,ans[N];double low[N],val[N];double map[N][N],MIN;double prim(){    int i,j;    double sum=0;    double tot=0;    for(i=1;i<=n;i++) low[i]=inf;    int u,v;    for(i=1;i<=n;i++)        if(mk[i])        {            u=i;            break;        }    sum+=val[u];    low[u]=-1;    for(i=u+1;i<=n;i++)        if(mk[i])        {            low[i]=map[u][i];            sum+=val[i];        }    for(i=1;i<=n-1;i++)    {        int minn=inf;        for(j=1;j<=n;j++)        {            if(mk[j]&&low[j]!=-1&&low[j]<minn)            {                minn=low[j];                v=j;            }        }        tot+=low[v];        low[v]=-1;        for(j=1;j<=n;j++)            if(low[j]!=-1&&mk[j]&&low[j]>map[v][j])                low[j]=map[v][j];    }    return tot/sum;}void dfs(int tot,int now){    int i;    if(tot>k) return ;    if(now==n+1)    {        if(tot!=k) return ;        double tmp=prim();        //printf("%lf\n",tmp);        if(tmp<MIN)        {            MIN=tmp;            for(i=1;i<=n;i++) ans[i]=mk[i];        }        return ;    }    else    {        mk[now]=1;        dfs(tot+1,now+1);        mk[now]=0;        dfs(tot,now+1);    }}int main(){    while(1)    {        int i,j;        scanf("%d%d",&n,&k);        if(n+k==0) break;        for(i=1;i<=n;i++) scanf("%lf",&val[i]);        for(i=1;i<=n;i++)            for(j=1;j<=n;j++)            {                scanf("%lf",&map[i][j]);                if(i==j) map[i][j]=inf;            }        MIN=inf;        memset(ans,0,sizeof(ans));        dfs(0,1);        for(i=1;i<=n;i++)            if(ans[i])            {                printf("%d",i);                break;            }        i++;        for(;i<=n;i++)            if(ans[i])            printf(" %d",i);        printf("\n");    }    return 0;}
View Code