题目链接:http://poj.org/problem?id=2728
01规划问题,二分+prim。注意这里的图是稠密图,应该用prim而不是kruskal。堆优化的prim不适合稠密图,也不适合邻接矩阵建图,否则基本上没怎么优化O(n*(lgn+n)),因为每次操作的常数因子很大,所以lgn与n的差别不大了,尤其在n比较小的时候。我这题用堆优化的prim居然还超时了!
1 //STATUS:C++_AC_1079MS_8124KB 2 #include<stdio.h> 3 #include<stdlib.h> 4 #include<string.h> 5 #include<math.h> 6 #include<iostream> 7 #include<string> 8 #include<algorithm> 9 #include<vector> 10 #include<queue> 11 #include<stack> 12 using namespace std; 13 #define LL __int64 14 #define pdi pair<double,int> 15 #define Max(a,b) ((a)>(b)?(a):(b)) 16 #define Min(a,b) ((a)<(b)?(a):(b)) 17 #define mem(a,b) memset(a,b,sizeof(a)) 18 #define lson l,mid,rt<<1 19 #define rson mid+1,r,rt<<1|1 20 const int N=1010,M=1000000,INF=0x3f3f3f3f,MOD=1999997; 21 const LL LLNF=0x3f3f3f3f3f3f3f3fLL; 22 const double DNF=100000000; 23 24 struct Node{ 25 int x,y,z; 26 }a[N]; 27 double w[N][N],d[N]; 28 int vis[N]; 29 int n; 30 31 inline double dist(Node &a,Node &b) 32 { 33 return sqrt((double)((a.x-b.x)*(a.x-b.x)+ 34 (a.y-b.y)*(a.y-b.y))); 35 } 36 /* 37 double prim(int s,double mid) 38 { 39 int i,u,v; 40 double sum=0,t; 41 priority_queue<pdi,vector<pdi>,greater<pdi> > q; 42 for(i=0;i<n;i++)d[i]=DNF;d[s]=0; 43 q.push(make_pair(0,s)); 44 mem(vis,0); 45 while(!q.empty()){ 46 u=q.top().second;q.pop(); 47 if(vis[u])continue; 48 vis[u]=1; 49 sum+=d[u]; 50 for(v=0;v<n;v++){ 51 if(!vis[v] && (t=abs(a[u].z-a[v].z)-mid*w[u][v])<d[v]){ 52 d[v]=t; 53 q.push(make_pair(t,v)); 54 } 55 } 56 } 57 return sum; 58 }*/ 59 double prim(int s,double mid) 60 { 61 int i,u,v,x; 62 double sum=0,t,m; 63 mem(vis,0); 64 for(i=0;i<n;i++)d[i]=DNF;d[s]=0; 65 for(i=0;i<n;i++){ 66 m=DNF; 67 for(x=0;x<n;x++)if(!vis[x] && d[x]<m)m=d[u=x]; 68 vis[u]=1; 69 sum+=d[u]; 70 for(v=0;v<n;v++){ 71 if(!vis[v] && (t=abs(a[u].z-a[v].z)-mid*w[u][v])<d[v]) 72 d[v]=t; 73 } 74 } 75 return sum; 76 } 77 78 double binary() 79 { 80 double l=0,r=200000,mid; 81 while(r-l>1e-4){ 82 mid=l+(r-l)/2; 83 if(prim(1,mid)<0)r=mid; 84 else l=mid; 85 } 86 return mid; 87 } 88 89 int main() 90 { 91 // freopen("in.txt","r",stdin); 92 int i,j; 93 while(~scanf("%d",&n) && n) 94 { 95 for(i=0;i<n;i++) 96 scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); 97 for(i=0;i<n;i++) 98 for(j=i;j<n;j++) 99 w[i][j]=w[j][i]=dist(a[i],a[j]); 100 101 printf("%.3lf\n",binary()); 102 } 103 return 0; 104 }