HDUOJ----2489 Minimal Ratio Tree

Minimal Ratio Tree

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2180    Accepted Submission(s): 630

Problem Description

For a tree, which nodes and edges are all weighted, the ratio of it is calculated according to the following equation.

Given a complete graph of n nodes with all nodes and edges weighted, your task is to find a tree, which is a sub-graph of the original graph, with m nodes and whose ratio is the smallest among all the trees of m nodes in the graph.

Input

Input contains multiple test cases. The first line of each test case contains two integers n (2<=n<=15) and m (2<=m<=n), which stands for the number of nodes in the graph and the number of nodes in the minimal ratio tree. Two zeros end the input. The next line contains n numbers which stand for the weight of each node. The following n lines contain a diagonally symmetrical n×n connectivity matrix with each element shows the weight of the edge connecting one node with another. Of course, the diagonal will be all 0, since there is no edge connecting a node with itself. All the weights of both nodes and edges (except for the ones on the diagonal of the matrix) are integers and in the range of [1, 100]. The figure below illustrates the first test case in sample input. Node 1 and Node 3 form the minimal ratio tree.

Output

For each test case output one line contains a sequence of the m nodes which constructs the minimal ratio tree. Nodes should be arranged in ascending order. If there are several such sequences, pick the one which has the smallest node number; if there's a tie, look at the second smallest node number, etc. Please note that the nodes are numbered from 1 .

Sample Input

3 2

30 20 10

0 6 2

6 0 3

2 3 0

2 2

1 1

0 2

2 0

0 0

Sample Output

1 3

1 2

Source

2008 Asia Regional Beijing

这道题是2008年北京现场比赛的一道题,题意大致意思是给定n个节点的一个图,要你从中选出这小边的权值和除以节点权值和的最小的一个树

于是很好理解的为最小生成树,采用普利姆最小生成树....注意精度的问题,这里我wa了n次

哎,喵了个咪

代码:

  1 #include<string.h>
  2 #include<stdlib.h>
  3 #include<stdio.h>
  4 #include<math.h>
  5 #define max 0x3f3f3f3f
  6 #define maxn 17
  7 int node_weight[maxn];
  8 int edge_weight[maxn][maxn];
  9 int depath[maxn];      //以这些点形成一颗最小生成树
 10 int  m , n ;
 11 double res;
 12 int stu[maxn];
 13 int sub_map[maxn][maxn];
 14 void Prime()
 15 {
 16   int vis[maxn]={0};
 17   int lowc[maxn];
 18   int i,j,k,minc;
 19   double ans=0;
 20   for(i=1;i<=m;i++)  //从n中挑出m个点形成一个子图
 21   {
 22     for(j=1;j<=m;j++)
 23     {
 24       if(edge_weight[depath[i]][depath[j]]==0)
 25          sub_map[i][j]=max;
 26       else
 27          sub_map[i][j]=edge_weight[depath[i]][depath[j]];
 28     }
 29   }
 30   vis[1]=1;
 31   for(i=1;i<=m;i++)
 32   {
 33     lowc[i]=sub_map[1][i];
 34   }
 35   for(i=2;i<=m;i++)
 36   {
 37      minc=max;
 38      k=0;
 39     for(j=2;j<=m;j++)
 40     {
 41       if(vis[j]==0&&minc>lowc[j])
 42         {
 43          minc=lowc[j];
 44          k=j;
 45         }
 46     }
 47     if(minc==max) return ;  //表示没有联通
 48     ans+=minc;
 49     vis[k]=1;
 50     for(j=1 ; j<=m;j++)
 51     {
 52         if(vis[j]==0&&lowc[j]>sub_map[k][j])
 53               lowc[j]=sub_map[k][j];
 54     }
 55   }
 56   int  sum=0;
 57    for(i=1;i<=m;i++)  //统计点权值的和
 58       sum+=node_weight[depath[i]];
 59       ans/=sum;
 60   if(res+0.00000001>=ans)
 61    {
 62        if((res>=ans&&res<=ans+0.000001)||(res<=ans&&res+0.000001>=ans+0.000001))
 63        {
 64            for(i=1;i<=m;i++)
 65            {
 66               if(stu[i]<depath[i]) return;
 67            }
 68        }
 69        res=ans;
 70        memcpy(stu,depath,sizeof(depath));
 71    }
 72 }
 73 void C_n_m(int st ,int count)
 74 {
 75     if(count==m)
 76     {
 77         Prime();
 78         return ;
 79     }
 80     for(int i=st ;i<=n;i++ )
 81     {
 82         depath[count+1]=i;
 83        C_n_m(i+1,count+1);
 84     }
 85 }
 86 int main()
 87 {
 88     int i,j;
 89     while(scanf("%d%d",&n,&m),m+n)
 90     {
 91         for(i=1;i<=n;i++)
 92            scanf("%d",node_weight+i);    //记录节点权值
 93         for(i=1;i<=n;i++)                //记录边权值
 94             for(j=1;j<=n;j++)
 95               scanf("%d",&edge_weight[i][j]);
 96       // C(n,m)
 97         res=max;
 98         C_n_m(1,0);
 99         for(i=1;i<=m;i++)
100         {
101            printf("%d",stu[i]);
102            if(i!=m)printf(" ");
103         }
104            putchar(10);
105     }
106     return 0;
107 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HDU 1556 Color the ball

Color the ball Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/327...

363110
来自专栏小樱的经验随笔

HDU 3782 xxx定律

xxx定律 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

36990
来自专栏码匠的流水账

聊聊HystrixCircuitBreaker

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixCircuitBreaker.java

8710
来自专栏ml

HDUOJ-------(1211)RSA

RSA Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/...

37090
来自专栏小樱的经验随笔

2017 Multi-University Training Contest - Team 9 1001&&HDU 6161 Big binary tree【树形dp+hash】

Big binary tree Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65...

28960
来自专栏JavaEdge

遨游springmvc之HandlerExceptionResolver1.前言2.原理4.总结

53850
来自专栏西安-晁州

Java基于ssm框架的restful应用开发

好几年都没写过java的应用了,这里记录下使用java ssm框架、jwt如何进行rest应用开发,文中会涉及到全局异常拦截处理、jwt校验、token拦截器等...

38560
来自专栏函数式编程语言及工具

Akka(26): Stream:异常处理-Exception handling

   akka-stream是基于Actor模式的,所以也继承了Actor模式的“坚韧性(resilient)”特点,在任何异常情况下都有某种整体统一的异常处理...

33680
来自专栏菩提树下的杨过

JAVA JPA - 示例用法

JPA(Java Persistence API)是JSR(Java Specification Requests)的一部分,定义了一系列对象持久化的标准,目前...

62460
来自专栏算法修养

PAT 甲级 1068 Find More Coins(0,1背包)

1068. Find More Coins (30) 时间限制 150 ms 内存限制 65536 kB 代码长度限制 16000 B ...

329110

扫码关注云+社区

领取腾讯云代金券