hdu 2489 Minimal Ratio Tree

http://acm.hdu.edu.cn/showproblem.php?pid=2489
この問題は,n個の点のうちm個の点を選択して生成ツリーを形成し,生成ツリーのratioを最小にすることである.暴力列挙+最小生成ツリー.

  1 #include <cstdio>

  2 #include <cstring>

  3 #include <algorithm>

  4 #define maxn 1000

  5 using namespace std;

  6 const int inf=1<<29;

  7 const double eps=1e-8;

  8 

  9 int map[maxn][maxn];

 10 int g[maxn][maxn];

 11 bool vis[maxn];

 12 int dis[maxn];

 13 int node[maxn];

 14 int ok[maxn];

 15 int w[maxn];

 16 int n,m;

 17 double ans;

 18 

 19 int prime()

 20 {

 21     memset(vis,false,sizeof(vis));

 22     for(int i=1; i<=m; i++) dis[i]=g[1][i];

 23     dis[1]=0;

 24     vis[1]=true;

 25     int sum1=0;

 26     for(int i=1; i<m; i++)

 27     {

 28         int x,m2=inf;

 29         for(int y=1; y<=m; y++) if(!vis[y]&&dis[y]<m2) m2=dis[x=y];

 30         vis[x]=true;

 31         sum1+=m2;

 32         for(int y=1; y<=m; y++) if(!vis[y]&&dis[y]>g[x][y]){

 33             dis[y]=g[x][y];

 34         }

 35     }

 36     return sum1;

 37 }

 38 

 39 

 40 void dfs(int u,int cnt)

 41 {

 42     node[cnt]=u;

 43     if(cnt>=m)

 44     {

 45         for(int i=1; i<=m; i++)

 46         {

 47             for(int j=1; j<=m; j++)

 48             {

 49                 g[i][j]=map[node[i]][node[j]];

 50             }

 51         }

 52         double edgew=prime()*1.0;

 53         double nodew=0.0;

 54         for(int i=1; i<=m; i++)

 55         {

 56             nodew+=w[node[i]];

 57         }

 58         double sum=edgew/nodew;

 59         if(ans-sum>=eps)

 60         {

 61             ans=sum;

 62             for(int i=1; i<=m; i++)

 63              ok[i]=node[i];

 64         }

 65     }

 66     for(int j=u+1; j<=n; j++)

 67     {

 68         dfs(j,cnt+1);

 69     }

 70 }

 71 

 72 int main()

 73 {

 74     while(scanf("%d%d",&n,&m)!=EOF)

 75     {

 76         memset(node,0,sizeof(node));

 77         memset(map,0,sizeof(map));

 78         memset(w,0,sizeof(w));

 79         memset(ok,0,sizeof(ok));

 80         if(n==0&&m==0) break;

 81         for(int i=1; i<=n; i++)

 82             scanf("%d",&w[i]);

 83         for(int i=1; i<=n; i++)

 84         {

 85             for(int j=1; j<=n; j++)

 86             {

 87                 scanf("%d",&map[i][j]);

 88             }

 89         }

 90         ans=inf;

 91         for(int i=1; i<=n; i++)

 92         {

 93             dfs(i,1);

 94         }

 95         for(int j=1; j<=m; j++)

 96         {

 97             if(j==1) printf("%d",ok[j]);

 98             else printf(" %d",ok[j]);

 99         }

100         printf("
");

101     }

102     return 0;

103 }

View Code