hdu 4756 Install Air Conditioning

Prim + 树形dp，南京网络赛的题目。这道题和12年福州现场赛的一道题很类似（hdu 4126 Genghis Khan the Conqueror），替换最小生成树上每一条边（与 0 点相连的边除外），然后分别求次小生成树，求生成树中的最大值。可以先prim求出最小生成树，再用dp求把边u - v 边删去，两颗子树的最短距离，分别替换求值就可以了。

#include<algorithm>  
#include<iostream>  
#include<cstring>  
#include<cstdio>  
#include<vector>  
#include<cmath>  
#define LL long long  
#define CLR(a, b) memset(a, b, sizeof(a))  
  
using namespace std;  
  
const int N = 1010;  
const double INF = 1e18;  
  
struct Edge  
{  
    int u, v;  
}E[N << 1];  
  
struct Point  
{  
    double x, y;  
}p[N];  
  
int n, fa[N];  
int fir[N], next[N << 1], tot;  
double d[N];  
bool vis[N];  
double map[N][N];  
double dp[N][N], pri;  
  
double len(Point a, Point b)  
{  
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));  
}  
  
void Add_Edge(int u, int v)  
{  
    E[tot].u = u, E[tot].v = v;  
    next[tot] = fir[u], fir[u] = tot ++;  
}  
  
void pre()  
{  
    int i, j;  
    for(i = 0; i < n; i ++)  
    {  
        dp[i][i] = INF;map[i][i] = 0;  
        for(j = i + 1; j < n; j ++)  
        {  
            map[j][i] = map[i][j] = len(p[i], p[j]);  
            dp[j][i] = dp[i][j] = INF;  
        }  
    }  
}  
  
void prim()  
{  
    int num = 1, u = 0, v, i, j;  
    double best = INF;tot = 0;  
    CLR(vis, 0);pri = 0;CLR(fir, -1);  
    for(i = 0; i < n; i ++) d[i] = INF;  
    while(num < n)  
    {  
        vis[u] = 1;best = INF;  
        for(i = 0; i < n; i ++)  
        {  
            if(!vis[i] && map[u][i] < d[i])  
            {  
                d[i] = map[u][i];  
                fa[i] = u;  
            }  
            if(!vis[i] && d[i] < best)  
            {  
                best = d[i];  
                j = i;  
            }  
        }  
        u = j;  
        Add_Edge(fa[j], j);  
        Add_Edge(j, fa[j]);  
        pri += map[fa[j]][j];  
        num ++;  
    }  
}  
  
double dfs(int pos, int u, int fa)  
{  
    int v, i, j;double cmp, ret = INF;  
    for(i = fir[u]; ~i; i = next[i])  
    {  
        v = E[i].v;  
        if(v != fa)  
        {  
            cmp = dfs(pos, v, u);  
            ret = min(ret, cmp);  
            dp[u][v] = dp[v][u] = min(dp[u][v], cmp);  
        }  
    }  
    if(fa != pos)  
        ret = min(ret, map[pos][u]);  
    return ret;  
}  
  
double dfs_ans(int u, int fa)  
{  
    int v, i;  
    double ret = 0;  
    for(i = fir[u]; ~i; i = next[i])  
    {  
        v = E[i].v;  
        if(v != fa)  
        {  
            ret = max(ret, pri - map[u][v] + dp[u][v]);  
            ret = max(ret, dfs_ans(v, u));  
        }  
    }  
    return ret;  
}  
  
int main()  
{  
    //freopen("input.txt", "r", stdin);  
    int t, i, v, k;double ans;  
    scanf("%d", &t);  
    while(t --)  
    {  
        scanf("%d%d", &n, &k);  
        for(i = 0; i < n; i ++)  
        {  
            scanf("%lf%lf", &p[i].x, &p[i].y);  
        }  
        pre();  
        prim();  
        for(i = 0; i < n; i ++)  
            dfs(i, i, -1);  
        ans = pri;  
        for(i = fir[0]; ~i; i = next[i])  
        {  
            v = E[i].v;  
            ans = max(ans, dfs_ans(v, 0));  
        }  
        printf("%.2lf\n", ans * k);  
    }  
}

补充：软件开发 , C++ ,