hdu 4756 Install Air Conditioning（2013南京网络赛） - c++编程基础

题意就是求MST中删去一条边后，次小生成树最大的那颗。注意题中说了“ there are so many wires between two specific dormitories” 。也就是说与0节点（power plant）相连的MST边是不会出故障的，所以要特殊考虑一下所有MST边都跟0节点相连的情况。

删除MST中某条边后的次小生成树用树形dp解决，传送门

我的理解是：删除MST边之后， MST被划分成u跟v两个子树，新添加的非MST边必然是连接u跟v两颗子树的原图中的非MST边，这可以用dfs解决。dp[u][v]代表两颗子树的最短距离，用每个点p的非MST边g[p][i]去更新所有的dp[u][v]，时间复杂度O(n^2)。

//#pragma comment(linker, "/STACK:1024000000,1024000000")  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define FF(i, a, b) for(int i=a; i=b; i--)  
#define REP(i, n) for(int i=0; i G[maxn];  
  
template  T sqr(T x) { return x*x; }  
double dist(int i, int j)  
{  
    return sqrt(sqr(x[i]-x[j]) + sqr(y[i] - y[j]));  
}  
  
void read()  
{  
    scanf("%d%lf", &n, &k);  
    REP(i, n) scanf("%lf%lf", &x[i], &y[i]);  
    REP(i, n)  
    {  
        FF(j, i+1, n) g[i][j] = g[j][i] = dist(i, j), dp[i][j] = dp[j][i] = INF;  
        g[i][i] = INF;  
        vis[i] = 0;  
        fa[i] = 0;  
        G[i].clear();  
    }  
}  
  
void prim()  
{  
    REP(i, n) d[i] = g[0][i];  
    vis[0] = 1;  
    fa[0] = -1;  
    d[0] = INF;  
    mst = 0;  
    FF(i, 1, n)  
    {  
        int pos = 0;  
        FF(j, 1, n) if(!vis[j] && d[pos] >




 d[j]) pos = j;  
  
        mst += d[pos];  
        vis[pos] = 1;  
  
        //构造MST  
        G[pos].PB(fa[pos]);  
        G[fa[pos]].PB(pos);  
  
        FF(j, 1, n) if(!vis[j] && g[pos][j] < d[j])  
            d[j] = g[pos][j], fa[j] = pos;  
    }  
}  
  
//用所有非MST边g[p][i] 更新所有dp[u][v]  
double dfs(int p, int u, int f)  
{  
    double ans = INF;  
    REP(i, G[u].size())  
    {  
        int v = G[u][i];  
        if(v != f)  
        {  
            double tmp = dfs(p, v, u);  
            ans = min(ans, tmp);  
            dp[u][v] = dp[v][u] = min(dp[u][v], tmp);  
        }  
    }  
    //保证非MST边才能更新  
    if(p != f) ans = min(ans, g[p][u]);  
    return ans;  
}  
  
double solve()  
{  
    REP(i, n) dfs(i, i, -1); //每个点更新一次  
  
    //MST中所有跟0节点相连的边是不会出问题的  
    bool flag = 0;  
    FF(i, 1, n) if(fa[0] != i && fa[i] != 0) flag = 1;  
    if(!flag) return mst * k;  
  
    double ret = 0;  
    //求MST边删除后的次小生成树的最大值  
    FF(i, 1, n) FF(j, i+1, n) if(fa[i] == j || fa[j] == i)ret = max(ret, dp[i][j] - g[i][j]);  
    return (mst + ret) * k;  
}  
  
int main()  
{  
    scanf("%d", &T);  
    while(T--)  
    {  
        read();  
        prim();  
        printf("%.2lf\n", solve());  
    }  
    return 0;  
}