首页 > 代码库 > HDU 2489 Minimal Ratio Tree(数据结构-最小生成树)
HDU 2489 Minimal Ratio Tree(数据结构-最小生成树)
Minimal Ratio Tree
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.
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.
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
Recommend
gaojie | We have carefully selected several similar problems for you: 2491 2485 2490 2492 2488
给你一张图n个点,每个点有权值,问你选出m个点,使得最小,输出方案。
解题思路:
用取与不取来枚举选出m个点的方案,既然m个点选定了,那么分母就确定了,分子通过最小生成树算出最小。
解题代码:
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; typedef long long ll; const int maxn=20; int n,m,d[maxn],a[maxn][maxn],cnt,father[maxn]; struct edge{ int u,v,w; edge(int u0=0,int v0=0,int w0=0){ u=u0,v=v0,w=w0; } friend bool operator <(edge x,edge y){ return x.w<y.w; } }e[maxn*maxn]; int find(int x){ if(father[x]!=x){ father[x]=find(father[x]); } return father[x]; } int getAns(vector <int> v){ for(int i=0;i<=n;i++) father[i]=i; cnt=0; for(int i=0;i<v.size();i++){ for(int j=0;j<v.size();j++){ if(a[v[i]][v[j]]) e[cnt++]=edge(v[i],v[j],a[v[i]][v[j]]); } } sort(e,e+cnt); int tmp=0; for(int i=0;i<cnt;i++){ if(find(e[i].u)!=find(e[i].v)){ father[find(e[i].v)]=find(e[i].u); tmp+=e[i].w; } } return tmp; } void solve(){ int ansm=1,ansz=(1<<30); vector <int> ansv; for(int i=0;i<(1<<n);i++){ vector <int> v; int tmpm=0; for(int t=0;t<n;t++){ if(i&(1<<t)){ v.push_back(t); tmpm+=d[t]; } } if(v.size()==m){ int tmpz=getAns(v); if((ll)tmpz*(ll)ansm<(ll)ansz*(ll)tmpm){ ansz=tmpz; ansm=tmpm; ansv=v; } } } for(int i=0;i<ansv.size();i++){ if(i>0) printf(" "); printf("%d",ansv[i]+1); } printf("\n"); } int main(){ while(scanf("%d%d",&n,&m)!=EOF && (m||n)){ for(int i=0;i<n;i++) scanf("%d",&d[i]); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ scanf("%d",&a[i][j]); } } solve(); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。