Install Air Conditioning HDU - 4756（最小生成树+树形dp）-白红宇

Install Air Conditioning HDU - 4756（最小生成树+树形dp）

阅读量：5793 次

发布时间：2019-06-18

本文共 2842 字，大约阅读时间需要 9 分钟。

题意是要让n-1间宿舍和发电站相连也就是连通嘛最小生成树板子一套

但是还有个限制条件就是其中有两个宿舍是不能连着的要求所有情况中最大的那个

这是稠密图用kruskal的时间会大大增加所以先跑一遍prim

跑完之后对最小生成树里面的边去搜索（树形dp）我觉得dp就是搜索（虽然我菜到切不了dp题。）

so dfs的过程我也叫做树形dp咯

dp[i][j]表示i和j不相连后这两个部分距离最小的边

代码如下

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int maxn = 1e3 + 10;const double inf = 0x3f3f3f3f3f3f;double d[maxn][maxn], lowc[maxn], dp[maxn][maxn];bool vis[maxn], is_tree[maxn][maxn];int pre[maxn], head[maxn];int cnt, n, m;double sum, ans;struct Point {    double x, y;} a[maxn];struct Edge {    int to, next;} edge[maxn<<1];inline double distan(const Point& lhs, const Point& rhs) {    return sqrt((lhs.x - rhs.x) * (lhs.x - rhs.x) + (lhs.y - rhs.y) * (lhs.y - rhs.y));}inline void addedge(int u, int v) {    edge[cnt].to = v;    edge[cnt].next = head[u];    head[u] = cnt++;}void Prim() {    sum = 0.0;    memset(vis, 0, sizeof(vis));    memset(pre, 0, sizeof(pre));    for (int i = 1; i < n; i++) lowc[i] = d[0][i];    vis[0] = true;    for (int i = 1; i < n; i++) {        double minc = inf;        int p = -1;        for (int j = 0; j < n; j++) {            if (!vis[j] && minc > lowc[j]) {                minc = lowc[j];                p = j;            }        }        sum += minc;        vis[p] = true;        addedge(p, pre[p]);        addedge(pre[p], p);        for (int j = 0; j < n; j++) {            if (!vis[j] && lowc[j] > d[p][j]) {                lowc[j] = d[p][j];                pre[j] = p;            }        }    }}double dfs(int u, int fa, int root) {    double ans = fa == root ? inf : d[root][u];    for (int i = head[u]; ~i; i = edge[i].next) {        int v = edge[i].to;        if (v == fa) continue;        double temp = dfs(v, u, root);        ans = min(ans, temp);        dp[u][v] = dp[v][u] = min(dp[u][v], temp);    }    return ans;}void dfs1(int u, int fa) {    for (int i = head[u]; ~i; i = edge[i].next) {        int v = edge[i].to;        if (v == fa) continue;        if (fa) ans = max(ans, sum - d[u][v] + dp[u][v]);        dfs1(v, u);    }}int main() {    int T;    scanf("%d", &T);    while (T--) {        scanf("%d%d", &n, &m);        for (int i = 0; i < n; i++) scanf("%lf%lf", &a[i].x, &a[i].y);        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                d[i][j] = d[j][i] = distan(a[i], a[j]);            }        }        cnt = 0;        memset(head, -1, sizeof(head));        Prim();        for (int i = 0; i < n; ++i)             for (int j = 0; j < n; ++j) dp[i][j] = inf;        for (int i = 0; i < n; i++) dfs(i, -1, i);        ans = sum;        dfs1(0, 0);        ans *= 1.0 * m;        printf("%.2f\n", ans);    }    return 0;}