本文主要是介绍AW348 沙漠之王（0/1分数规划-Dinkelbach），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址
易错点：
- double类型不初始化为0就爆炸.
- 每次prim前需要先从首都向每个村庄加边.
- "长度"指二维欧氏距离.
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=2e3,INF=1<<30;
struct village{int x,y,z;
}villages[MAXN];
double getDis(village a,village b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.z-b.z)*(a.z-b.z));
}
int n,pre[MAXN];
bool vis[MAXN];
double minw[MAXN],cost[MAXN][MAXN],len[MAXN][MAXN];
double prim(double k){memset(vis,0,sizeof(vis));vis[1]=1;for(int i=2;i<=n;i++){minw[i]=cost[1][i]-len[1][i]*k;pre[i]=1;}double Cost,Len;Cost=Len=0;//不初始化就爆炸 for(int i=1;i<=n;i++){double nowMin=INF;int nowV=0;for(int j=1;j<=n;j++){if(!vis[j]&&minw[j]<nowMin){nowMin=minw[nowV=j];}}vis[nowV]=1;Cost+=cost[pre[nowV]][nowV],Len+=len[pre[nowV]][nowV];for(int j=1;j<=n;j++){double tmp=cost[nowV][j]-k*len[nowV][j];if(!vis[j]&&tmp<minw[j]){minw[j]=tmp;pre[j]=nowV;}}}return Cost/Len;
}
void init(){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cost[i][j]=fabs(villages[i].y-villages[j].y);len[i][j]=getDis(villages[i],villages[j]);}}
}
int main(){while(~scanf("%d",&n)){if(n==0)break;for(int i=1;i<=n;i++){int x,y,z;scanf("%d%d%d",&villages[i].x,&villages[i].z,&villages[i].y);}init();double a,b;while(1){b=prim(a);if(fabs(b-a)<1e-4)break;a=b;}printf("%.3f\n",a);}return 0;
}
这篇关于AW348 沙漠之王（0/1分数规划-Dinkelbach）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
