想到枚举m个点,然后求最小生成树,ratio即为最小生成树的边权/总的点权。
但是怎么枚举这m个点,实在不会。
网上查了一下大牛们的解法,用dfs枚举,没想到dfs还有这么个作用。
参考链接:http://blog.****.net/xingyeyongheng/article/details/9373271
#include <stdio.h>
#include <string.h>
#include <set>
#include <vector>
#include <queue> using namespace std; const int INF=0x3f3f3f3f;
int n,m,tot; //tot为选取的m个点的总权值
int choseNode[]; //存储选取的m个点
int tmp[]; //存储最小ratio的m个点
int nodew[],w[][]; //nodew[i]存储点i的权值,w[i][j]存储边的权值
int dis[],vis[];
double minratio=0x3f3f3f3f; int prim(){
int ans=;
memset(dis,INF,sizeof(dis));
memset(vis,,sizeof(vis));
int t,idx;
dis[choseNode[]]=;
for(int i=;i<=m;i++){
t=INF;
for(int i=;i<m;i++){
if(!vis[choseNode[i]] && dis[choseNode[i]]<t){
t=dis[choseNode[i]];
idx=choseNode[i];
}
}
vis[idx]=;
ans+=t;
for(int i=;i<m;i++){
int u=choseNode[i];
if(!vis[u] && w[idx][u]<dis[u]){
dis[u]=w[idx][u];
}
}
}
return ans;
}
/*
dfs枚举m个点,num代表目前选取了多少个点,k代表第num个点为k。
表示前num个点选自1~k,剩余的点从k+1~n中选。
*/
void dfs(int k,int num){
if(num==m){
tot=;
for(int i=;i<m;i++){
tot+=nodew[choseNode[i]];
}
int sum=prim();
double tmpratio=sum*1.0/tot;
if(tmpratio<minratio){
minratio=tmpratio;
for(int i=;i<m;i++){
tmp[i]=choseNode[i];
}
}
return; //忘记写return了。。。
}
//若剩余的点的个数(n-k)加上目前选取的个数num小于m的话,说明即使接下来n-k个点都选取,也选不足m个点,直接return
if(n-k+num<m)
return;
for(int i=k+;i<=n;i++){
//选的点用数组存起来
choseNode[num]=i;
dfs(i,num+);
}
}
int main()
{
int a;
while(scanf("%d%d",&n,&m)!=EOF){
if(n== && m==)
break;
memset(w,,sizeof(w));
minratio=INF*0.1;
for(int i=;i<=n;i++){
scanf("%d",&nodew[i]);
}
for(int i=;i<=n;i++){
for(int j=;j<=i;j++)
scanf("%d",&a);
for(int j=i+;j<=n;j++){
scanf("%d",&a);
w[i][j]=w[j][i]=a;
}
}
for(int i=;i<=n;i++){
choseNode[]=i;
dfs(i,);
}
for(int i=;i<m-;i++){
printf("%d ",tmp[i]);
}
printf("%d",tmp[m-]);
printf("\n");
}
return ;
}
最后再附上网上看到的另一种dfs枚举的写法:
//调用时:dfs(1,0,0); //dep表示点的编号,cnt表示选取的点的个数,sum_pw表示目前选取了cnt个点后总的点权值
void dfs(int dep, int cnt, int sum_pw) {
if(cnt == m) {
...;
return ;
}
if(dep == n + ) return ;
use[dep] = true; //选取点dep,这里use[i]=true表示选取点i,在用prim求最小生成树的时候有用
dfs(dep + , cnt + , sum_pw + weight[dep]);
use[dep] = false; //不选取点dep
dfs(dep + , cnt, sum_pw);
}