題意：

給定N個平面上的點的坐標和它們的權值，任意兩點之間的邊的價值是它們的距離，費用是兩點權值之差的絕對值，求該圖的一棵生成樹，使得該樹所有邊的費用之和與價值之和的比值最小（只需求這個比值即可）

題解：

詳細內容可以看看這個的第二個模型
01分數規劃模型，如果ei∈T則xi = 1 否則 xi =0
二分答案r
如何驗證答案r？
邊賦權ans[i] = value[i] - r * cost[i]
因為是生成樹，邊的數量確定，那么max{f( r )}需要取前n-1大的ans[i],也就是求最大生成樹，按最大生成樹權值的正負性來二分，最小化就是求最小生成樹
我這里說幾點，二分循環時用while(r-l>=1e-5)
本題是用的prim（因為是稠密圖）求的最小生成樹

代碼：

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<set> #include<map> #include<vector> #include<queue> using namespace std; #define ll long long #define sqr(x) (1.0*(x)*(x)) #define RG register #define MAX 1111 inline int read() {RG int x=0,t=1;RG char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=-1,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return x*t; } int n,x[MAX],y[MAX],z[MAX]; double dis[MAX]; double len[MAX][MAX],cost[MAX][MAX],g[MAX][MAX]; bool vis[MAX]; bool check(double mid) {for(int i=0;i<=n;++i)dis[i]=1e20,vis[i]=false;dis[1]=0;double tot=0;for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)g[i][j]=cost[i][j]-mid*len[i][j];for(int i=1;i<=n;++i){int u=0;for(int j=1;j<=n;++j)if(!vis[j]&&dis[j]<dis[u])u=j;vis[u]=true;tot+=dis[u];for(int j=1;j<=n;++j)if(!vis[j])dis[j]=min(dis[j],g[u][j]);}return tot<=0; } int main() {while(n=read()){for(int i=1;i<=n;++i)x[i]=read(),y[i]=read(),z[i]=read();for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){len[i][j]=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));cost[i][j]=abs(z[i]-z[j]);}double l=0,r=1e5;while(r-l>=1e-5){double mid=(l+r)/2;if(check(mid))r=mid;else l=mid;}printf("%.3f\n",l);}return 0; }

總結

以上是生活随笔為你收集整理的Desert King POJ - 2728的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。