hdu2489:http://acm.hdu.edu.cn/showproblem.php?pid=2489
题意：给你一个n个节点图，图的点有边权和点权，然后选取m个节点的子图，然后求这个一棵树，然后让这棵树的所有边权之和/所有点权之和的值最少。
题解：n很小，只有15，所以可以直接暴力，枚举每一种情况，然后求每一种情况的最小生成树，取最小的就可以了。但是这里的学到一个新的东西。就是判断a<b的时候，有可能a==b的时候由于浮点误差，也会被判成a<b,但是题目要的是字典序最小的，所以相等的时候是不能取的，所以要先考虑a和b是否相等，在不等的情况下在进行a<b的判断。
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
int fa[],node[],ans[],val[],g[][];
int n,m;
double last;
void init(){
for(int i=;i<=;i++)
fa[i]=i;
}
int Find(int x){
int s;
for(s=x;s!=fa[s];s=fa[s]);
while(x!=s){
int temp=fa[x];
fa[x]=s;
x=temp;
}
return s;
}
struct Node{
int x,y;
int w;
bool operator<(const Node a)const{
return w<a.w;
}
}num[];
void solve(int *a){
int top=,cost=;
for(int i=;i<=n;i++)
if(a[i])cost+=val[i]; for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(a[i]&&a[j]&&g[i][j]){
num[++top].x=i;
num[top].y=j;
num[top].w=g[i][j];
}
sort(num+,num+top+);
int ct1=,ct2=;
init();
for(int i=;i<=top;i++){
int tx=Find(num[i].x);
int ty=Find(num[i].y);
if(tx==ty)continue;
else{
fa[tx]=ty;
ct1+=num[i].w;
ct2++;
if(ct2==m-)break;
}
}
if(ct2==m-){
double temp=(double)ct1/(double)cost;
if(abs(temp-last)>0.00000001&&temp<last){
last=temp;
memset(ans,,sizeof(ans));
for(int i=;i<=n;i++)
if(a[i])
ans[i]=i;
}
}
}
void DFS(int depth,int start){
if(depth==m+){
solve(node);
return;
}
for(int i=start;i<=n;i++){
node[i]=;
DFS(depth+,i+);
node[i]=;
}
}
int main(){
while(~scanf("%d%d",&n,&m)&&n){
memset(g,,sizeof(g));
memset(ans,,sizeof(ans));
memset(node,,sizeof(node));
for(int i=;i<=n;i++)
scanf("%d",&val[i]);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&g[i][j]);
last=100000000.0;
DFS(,);
int aa=;
for(int i=;i<=n;i++)
if(ans[i]){
if(!aa)printf("%d",ans[i]);
else
printf(" %d",ans[i]);
aa=;
}
puts("");
}
}