最小生成树 Kruskal

Kruskal适用于点比较多边比较少的情况(稀疏图)

HDU 1875 畅通工程再续

#include <cstdio>
#include <cmath>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;

const int MAXN = 1000 + 5;
const double eps = 0;

int fa[MAXN];

struct point {
    double x, y;
}p[MAXN];

double dis(int i, int j) {
    return 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));
}

struct edge {
    int u, v;
    double w;
    bool operator < (const edge &rhs) const {
        return w < rhs.w;
    }
} e[MAXN * MAXN];

int findfa(int u) {
    if (fa[u] != u) fa[u] = findfa(fa[u]);
    return fa[u];
}

int m;
double cost;

void unin(int u, int v, double w) {
    int fau = findfa(u);
    int fav = findfa(v);
    if (fau == fav) return;
    if (fau < fav) {
        fa[fav] = fau;
    } else {
        fa[fau] = fav;
    }
    cost += w;
    m--;
}

int main() {
    //freopen("in.txt", "r", stdin);
    int n, t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }

        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                e[cnt].u = i;
                e[cnt].v = j;
                e[cnt++].w = dis(i, j);
            }
        }

        sort(e, e + cnt);
        m = n - 1, cost = 0;
        for (int i = 0; i < cnt; i++) {
            if (m == 0) break;
            //if (e[i].w < 10 || e[i].w  > 1000) continue;
            if (e[i].w - 10 < eps || e[i].w - 1000 > eps) continue;
            unin(e[i].u, e[i].v, e[i].w);
        }

        if (!m) printf("%.1f\n", cost * 100.0);
        else puts("oh!");
    }
    return 0;
}

HDU 4081 Qin Shi Huang’s National Road System

给出一个图，每个节点是一个城市，权值代表人口，城市间的距离里为欧基里德距离。现在求这个图的一个生成树，使A/B尽可能的大，其中A是生成树的某条边的两个节点上人口数的和，B是这个生成树上除了刚才选中的那条边之外的所有边的距离的和

要B尽可能的小，先求原图的一个最小生成树，要添加一条边并替换最小生成树上的某一条边，使它仍是一个树。枚举要添加的边，维护一个A/B的最大值，即可求出答案，如果这条边是原生成树上的边，设原来的最小生成树上的边权和为EW，则B = EW – e[i].w; 如果要添加的边不是原来最小生成树上的边，B = EW – maxd[e[i].u][e[i].v]，maxd[i][j]表示在生成树上从i点到j点路上最长边的值

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN = 1000 + 50;
int tot, cnt, n;

int head[MAXN], fa[MAXN], vis[MAXN];
double maxd[MAXN][MAXN];
bool G[MAXN][MAXN];

struct Edge{
    int u, v;
    double w;
    bool operator < (const Edge &rhs) const {
        return w < rhs.w;
    }
}E[MAXN * MAXN];

struct edge{
    int to, nxt;
    double cost;
}e[MAXN << 2];

void init() {
    tot = 0, cnt = 0;
    memset(head, -1, sizeof(head));
    memset(maxd, 0, sizeof(maxd));
    memset(G, 0, sizeof(G));
}

void addedge(int u, int v, double w) {
    e[tot].to = v;
    e[tot].cost = w;
    e[tot].nxt = head[u];
    head[u] = tot++;
}

struct point {
    int x, y;
    double w;
}p[MAXN];

void bfs(int s) {
    queue<int>q;
    memset(vis, 0, sizeof(vis));
    vis[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i != -1; i = e[i].nxt) {
            int v = e[i].to;
            if (vis[v]) continue;
            maxd[s][v] = maxd[v][s] = max(maxd[s][u], e[i].cost);
            q.push(v);
            vis[v] = 1;
        }
    }
}

void dfs(int rt, int u, int fa, double md) {
    for (int i = head[u]; i != -1; i = e[i].nxt) {
        int v = e[i].to;
        if (v == fa) continue;
        maxd[rt][v] = maxd[v][rt] = max(md, e[i].cost);
        dfs(rt, v, u, maxd[rt][v]);
    }
}

int findfa(int u) {
    if (fa[u] != u) fa[u] = findfa(fa[u]);
    return fa[u];
}

double kru(int n) {
    int m = n - 1;
    double ew = 0;
    for (int i = 0; i <= n; i++) fa[i] = i;
    sort(E, E + cnt);
    for (int i = 0; i < cnt; i++) {
        int u = E[i].u, v = E[i].v;
        double  w = E[i].w;
        int fau = findfa(u);
        int fav = findfa(v);
        if (fau == fav) continue;
        if (fau > fav) swap(fau, fav);
        fa[fav] = fau;
        ew += E[i].w;
        addedge(u, v, w);
        addedge(v, u, w);
        G[u][v] = G[v][u] = 1;
        if(--m <= 0) break;
    }
    return ew;
}

double dis(int i, int j) {
    return 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));
}

int main() {
    //freopen("in.txt", "r", stdin);
    int t;
    scanf("%d", &t);
    while (t--) {
        init();
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d%d%lf", &p[i].x, &p[i].y, &p[i].w);

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                E[cnt].u = i;
                E[cnt].v = j;
                E[cnt++].w = dis(i, j);
            }
        }

        double ew = kru(n);
        //for (int i = 1; i <= n; i++) dfs(i, i, -1, 0);
        for (int i = 1; i <= n; i++) bfs(i);

        double ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                ans = max(ans, (p[i].w + p[j].w) / (ew - maxd[i][j]));
            }
        }
        printf("%.2f\n", ans);
    }
    return 0;
}