hdu 4081 Qin Shi Huangs National Road System(次小生成樹變形)

枚舉每條邊<u, v>, ans=(val[u]+val[v]) / (prim - g[u][v])；

而prim則是包含邊<u, v>的生成樹中最小的那個權值和。

先求出原圖的最小生成樹。use[u][v] = 2時，邊<u, v>在MST上， use[u][v] = 1時，存在邊<u, v>。

f[u][v]表示u->v的最小瓶頸路。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<fstream>
#include<sstream>
#include<bitset>
#include<vector>
#include<string>
#include<cstdio>
#include<cmath>
#include<stack>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i<n; i++)
#define CLR(a, b) memset(a, b, sizeof(a))
#define debug puts("**debug**")
#define LL long long
#define PB push_back
using namespace std;

const int maxn = 1010;
const double INF = 1e10;
int n, m, T, use[maxn][maxn];
double g[maxn][maxn], f[maxn][maxn], val[maxn];
double ans1, ans2;

double prim()
{
    int pre[maxn] = {-1};
    bool vis[maxn] = {0};
    double d[maxn], ret = 0;
    FF(i, 1, n+1) d[i] = INF;   d[1] = 0;
    FF(i, 1, n+1)
    {
        int pos;
        double tmp = INF;
        FF(j, 1, n+1) if(!vis[j] && d[j] < tmp) tmp = d[j], pos = j;
        if(pre[pos] != -1)
        {
            use[pre[pos]][pos] = use[pos][pre[pos]] = 2;
            FF(j, 1, n+1) if(vis[j]) f[pos][j] = f[j][pos] = max(f[j][pre[pos]], g[pre[pos]][pos]);
        }
        vis[pos] = 1;
        ret += d[pos];
        FF(j, 1, n+1) if(!vis[j] && use[pos][j] && g[pos][j] < d[j]) d[j] = g[pos][j], pre[j] = pos;
    }
    return ret;
}

double Second_MST()
{
    ans1 = prim();
    ans2 = -1;
    FF(i, 1, n+1) FF(j, i+1, n+1)
    {
        double A = val[i] + val[j], B;
        if(use[i][j] == 2) B = ans1 - g[i][j];
        else if(use[i][j] == 1) B = ans1 - f[i][j];
        ans2 = max(ans2, A/B);
    }
    return ans2;
}

struct Point
{
    double x, y;
}p[maxn];

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);

        FF(i, 1, n+1) scanf("%lf%lf%lf", &p[i].x, &p[i].y, &val[i]);

        FF(i, 1, n+1) FF(j, i+1, n+1)
        {
            g[i][j] = g[j][i] = sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x) + (p[i].y-p[j].y)*(p[i].y-p[j].y));
            use[i][j] = use[j][i] = 1;
            f[i][j] = f[j][i] = 0;
        }

        printf("%.2lf\n", Second_MST());
    }
    return 0;
}