刘汝佳新书--训练指南
题意：秦朝有n个城市，需要修建一些道路使得任意两个城市之间都可以连通。道士徐福声称他可以用法术修路，不花钱，也不用劳动力，但只能修一条路，因此需要慎重选择用那一条路。秦始皇不仅希望其他道路总长度B尽量短，还希望法术连接的两个城市的人口之和A尽量大，因此下令寻找一个使A/B最大的方案。你的任务是找出这个方案
分析：先求出最小生成树，在枚举边u-v之后删除最小生成树中u和v之间唯一路径上的最大权maxcost[u][v]。只需在预处理时用O(n^2)时间算出maxcost数组，问题得到解决
// File Name: 1494.cpp // Author: zlbing // Created Time: 2013/2/15 22:15:54 #include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include<stack> #include<cmath> #include<queue> using namespace std; #define MAXN 1050 struct Edge{ int from,to; double w; bool operator<(const Edge& a)const{ return a.w>w; } }edges[MAXN*MAXN]; int Edge_len; struct NODE{ int x,y,p; }P[MAXN]; int f[MAXN]; vector<int>G[MAXN]; vector<Edge>tree_edge; double g[MAXN][MAXN]; bool vis[MAXN]; double judge(NODE a,NODE b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int find(int x) { return f[x]==x?x:f[x]=find(f[x]); } void dfs(int u,int n)//dfs算出maxcost数组也就是g数组 { vis[u]=true; for(int i=0;i<G[u].size();i++) { Edge& e=tree_edge[G[u][i]]; if(vis[e.to])continue; g[e.to][e.from]=g[e.from][e.to]=e.w; for(int i=0;i<n;i++) if(vis[i]) g[e.to][i]=g[i][e.to]=max(g[i][e.from],g[e.from][e.to]); dfs(e.to,n); } } void kruscal(int n) { double sum=0,ans=0; for(int i=0;i<n;i++)f[i]=i; sort(edges,edges+Edge_len); for(int i=0;i<n;i++)G[i].clear(); tree_edge.clear(); for(int i=0;i<Edge_len;i++) { int x=find(edges[i].from); int y=find(edges[i].to); if(x!=y) { sum+=edges[i].w; f[y]=x; //形成一颗最小生成树 tree_edge.push_back((Edge){edges[i].from,edges[i].to,edges[i].w}); int m=tree_edge.size(); G[edges[i].from].push_back(m-1); tree_edge.push_back((Edge){edges[i].to,edges[i].from,edges[i].w}); m=tree_edge.size(); G[edges[i].to].push_back(m-1); } } memset(g,0,sizeof(g)); memset(vis,false,sizeof(vis)); dfs(0,n); for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) ans=max(ans,(P[i].p+P[j].p)/(sum-g[i][j])); printf("%.2lf\n",ans); } int main(){ int N,n; scanf("%d",&N); while(N--) { scanf("%d",&n); int a,b,c; for(int i=0;i<n;i++) { scanf("%d%d%d",&a,&b,&c); a--,b--; P[i].x=a,P[i].y=b,P[i].p=c; } Edge_len=0; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) { edges[Edge_len].from=i; edges[Edge_len].to=j; edges[Edge_len].w=judge(P[i],P[j]); Edge_len++; } kruscal(n); } return 0; }