2011年 ACM/ICPC 北京赛区 A题 Qin shi huang's national road system

现场其实想到了找两点间最大边，但是一直在想DFS找的方法，期间我也想了想预处理的可行性，可是想岔道了，觉得不可行，结果今天用类似DP的预处理终于给过了，我擦了，铁牌第一名，要多点背有多点背。莫非是RP用光了，希望明年能好点吧。

这道题的解法其实有两种，另一种是先求一棵最小生成树，然后枚举每一条最小生成树上的边，拆掉后变成两个生成树，然后找两个集合中点权最大的两个连接起来，这是暴力贪心策略。而正解是北大教练讲的，先求一棵最小生成树，通过类似DP的预处理将每两点之间的最大边求出来，然后，一个二重循环枚举每对点，减掉最大边，添上点权就行。

/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 10005
#define INF 100000000
#define eps 1e-11
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
double d[1005][1005]; //存储两点间距离
double dis[1005]; 
bool used[1005];
int n;
double mx[1005][1005];
int near[1005]; //记录每次所加的边，如果near[i] = -1 就说明顶点i已经加到生成树中了。
struct point
{double x, y;int po;
} p[1005];
double distan(point x, point y)
{return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
}
int main()
{
#ifdef LOCALfreopen("d:/data.in","r",stdin);freopen("d:/data.out","w",stdout);
#endifint T, i, j, n;scanf("%d", &T);while(T--){scanf("%d", &n);for(i = 1; i <= n; i++)scanf("%lf%lf%d", &p[i].x, &p[i].y, &p[i].po);for(i = 1; i <= n; i++){for(j = 1; j <= n; j++){d[i][j] = d[j][i] = distan(p[i], p[j]);mx[i][j] = 0;}}memset(used, false, sizeof(used));for(i = 1; i <= n; i++){dis[i] = d[1][i];near[i] = 1;}used[1] = true;double B = 0;int A;near[1] = -1;for(i = 1; i < n; i++){int mi = INF;int v = -1;for(j = 1; j <= n; j++){if(near[j] != -1 && dis[j] < mi){v = j;mi = dis[j];}}int pre;if(v != -1){pre = near[v];B += d[v][near[v]];//printf("%d %d ddd\n", near[v], v);mx[near[v]][v] = mx[v][near[v]] = d[v][near[v]]; //邻接的点之间的最大边是自己near[v] = -1;for(j = 1; j <= n; j++){if(near[j] != -1 && d[v][j] < dis[j]){dis[j] = d[v][j];near[j] = v;}}}for(j = 1; j <= n; j++){if(near[j] == -1 && j != v){mx[j][v] = mx[v][j] = max(mx[j][pre], mx[pre][v]); //转移方程，代表j到v的最大边为j到pre和pre到v的最大边中的大的。}}}double ans = 0;for(i = 1; i <= n; i++) //二重循环遍历{for(j = 1; j <= n; j++){if(i == j) continue;A = p[i].po + p[j].po;if((double)A / (B - mx[i][j]) > ans)ans = (double)A / (B - mx[i][j]);}}printf("%.2f\n", ans);}return 0;
}