http://acm.hdu.edu.cn/showproblem.php?pid=4081
解题报告:
先求最小生成树，并把这棵树记录下来，用low，和pre数组
然后dp数组表示最大边，这个信息可以在求prim的时候得到。
然后不断枚举任意两点修魔法路。那么这条路可能在最小生成树上，或者不在。
如果不在则替换到这两点之间的在mst上的最长路。dp数组
如果在咋直接替换到mst上的路 也是dp数组
View Code
#include<iostream> #include<string.h> #include<stdio.h> #include<algorithm> #include<cmath> using namespace std; #define maxn 1110 #define inf ~0U>>1 double map[maxn][maxn]; double people[maxn]; double low[maxn]; double max(double a,double b) { return a>b?a:b; } struct node0 { double x; double y; }node[maxn]; double dp[maxn][maxn]; int n; int visit[maxn]; int pre[maxn]; double sum; double len(double x1,double y1,double x2,double y2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } void init() { memset(people,0,sizeof(people)); for(int i=0;i<=maxn;i++) for(int j=0;j<=maxn;j++) map[i][j]=inf; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&node[i].x,&node[i].y,&people[i]); } void MAP() { for(int i=1;i<n;i++) { for(int j=i+1;j<=n;j++) { map[i][j]=map[j][i]=len(node[i].x,node[i].y,node[j].x,node[j].y); } } } double prim() { double temp; int id; double ans=0; memset(visit,0,sizeof(visit)); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++)pre[i]=1; for(int i=1;i<=maxn;i++)low[i]=inf; visit[1]=1; for(int i=2;i<=n;i++) low[i]=map[1][i]; for(int i=2;i<=n;i++) { temp=inf; for(int j=1;j<=n;j++) if(!visit[j]&&low[j]<temp) temp=low[j],id=j; ans+=temp,visit[id]=1; for(int j=1;j<=n;j++) if(visit[j]&&id!=j) dp[id][j]=dp[j][id]=max(dp[pre[id]][j],temp); for(int j=1;j<=n;j++) if(low[j]>map[id][j]&&!visit[j]) low[j]=map[id][j],pre[j]=id; } return ans; } double solve() { double temp=0.0; double ans=0.0; for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) { temp=(people[i]+people[j])/(sum-dp[i][j]); ans=max(temp,ans); } return ans; } int main() { int test; for(cin>>test;test;test--) { init(); MAP(); sum=prim(); printf("%.2f\n",solve()); } return 0; }