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

时间：2024-12-25 11:04:38

Install Air Conditioning

HDU - 4756

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

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

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

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

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

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

代码如下

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>

using namespace std;

const int maxn = 1e3 + ;

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<<];

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, , sizeof(vis));

    memset(pre, , sizeof(pre));

    for (int i = ; i < n; i++) lowc[i] = d[][i];

    vis[] = true;

    for (int i = ; i < n; i++) {

        double minc = inf;

        int p = -;

        for (int j = ; 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 = ; 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 = ; i < n; i++) scanf("%lf%lf", &a[i].x, &a[i].y);

        for (int i = ; i < n; i++) {

            for (int j = i + ; j < n; j++) {

                d[i][j] = d[j][i] = distan(a[i], a[j]);

            }

        }

        cnt = ;

        memset(head, -, sizeof(head));

        Prim();

        for (int i = ; i < n; ++i)

            for (int j = ; j < n; ++j) dp[i][j] = inf;

        for (int i = ; i < n; i++) dfs(i, -, i);

        ans = sum;

        dfs1(, );

        ans *= 1.0 * m;

        printf("%.2f\n", ans);

    }

    return ;

}

最小生成树的各种题型根本没掌握...新生赛后要补补这块和并查集的坑了...

相关文章