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

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

Run ID Problem ID Status Time Memory Language Code Submit At User

15470

238

Accepted

216ms

15956kb

G++

3153B

2011-10-25 08:44:20

maddoctor

这道题的解法其实有两种，另一种是先求一棵最小生成树，然后枚举每一条最小生成树上的边，拆掉后变成两个生成树，然后找两个集合中点权最大的两个连接起来，这是暴力贪心策略。而正解是北大教练讲的，先求一棵最小生成树，通过类似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 LOCAL
    freopen("d:/data.in","r",stdin);
    freopen("d:/data.out","w",stdout);
#endif
    int 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;
}