最小树形图

有向图的最小生成树，建好图直接套模板

POJ 3164 Command Network

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

const int MAXN = 100 + 5;
const int MAXM = 10000 + 5;
const double INF = 1e9;

bool G[MAXN][MAXN];
int pre[MAXN], id[MAXN], vis[MAXN];
int cnt;
double in[MAXN];

struct point {
    double x, y;
    double dis(const point & p) const {
        return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
    }
}p[MAXN];

struct edge{
    int u, v;
    double w;
}e[MAXM];

void addedge(int u, int v, double w) {
    e[cnt].u = u;
    e[cnt].v = v;
    e[cnt++].w = w;
}

double zl(int rt, int n, int m) {
    double ans = 0;
    int v;
    while (1) {
        for (int i = 0; i < n; i++) in[i] = INF;
        for (int i = 0; i < m; i++) {
            if (e[i].w < in[e[i].v]) {
                pre[e[i].v] = e[i].u;
                in[e[i].v] = e[i].w;
            }
        }
        for (int i = 0; i < n; i++) {
            if (i != rt && in[i] == INF) {
                return -1.0;
            }
        }
        int tn = 0;
        memset(id, -1, sizeof(id));
        memset(vis, -1, sizeof(vis));
        in[rt] = 0;
        for (int i = 0; i < n; i++) {
            ans += in[i];
            v = i;
            while (vis[v] == -1 && v != rt) {
                vis[v] = i;
                v = pre[v];
            }
            if (v != rt && vis[v] == i) {
                for (int u = pre[v]; u != v; u = pre[u]) {
                    id[u] = tn;
                }
                id[v] = tn++;
            }
        }
        if (tn == 0) break;
        for (int i = 0; i < n; i++) {
            if (id[i] == -1) id[i] = tn++;
        }
        for (int i = 0; i < m;) {
            v = e[i].v;
            e[i].u = id[e[i].u];
            e[i].v = id[e[i].v];
            if (e[i].u != e[i].v) {
                e[i++].w -= in[v];
            } else {
                swap(e[i], e[--m]);
            }
        }
        n = tn;
        rt = id[rt];
    }
    return ans;
}



int main() {
    //freopen("in.txt", "r", stdin);
    int n, m, u, v;
    while (scanf("%d%d", &n, &m) != EOF) {
        for (int i = 0; i < n; i++) {
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        memset(G, 0, sizeof(G));
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &u, &v);
            if (u != v) G[u-1][v-1] = 1;
        }
        cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!G[i][j]) continue;
                addedge(i, j, p[i].dis(p[j]));
            }
        }
        double ans = zl(0, n, cnt);
        if (ans == -1.0) puts("poor snoopy");
        else printf("%.2f\n", ans);
    }
    return 0;
}

HDU 4009 Transfer water

在山上有N户人家，每家的坐标为(xi, yi, zi)。每户人家要吃水，要么自己打井，花费为A zi，要么从别人的家引水渠代价为B 两家的曼哈顿距离，如果这家的海拔比供水的低，还要另外再买一个价值为C的水泵。问每家都有水吃的最低花费是多少。

每家都有水的目标一定能达成，大不了每家都打口井…

把所有能连水渠的两家连起来，就得到了一个有向图，答案一定一个森林。建立一个虚节点，向每个点连一条有向边，权值为在第i家挖井的代价，这样就把答案从森林变成了一棵树，求全图的一个最小树形图就是最低的代价。

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

const int MAXN = 1000 + 5;
const int MAXM = 1000000 + 5;
const int INF = 0x3f3f3f3f;

int pre[MAXN], id[MAXN], vis[MAXN];
int cnt;
int in[MAXN];

struct point {
    int x, y, z;
    int dis(const point & p) const {
        return (abs(x - p.x) + abs(y - p.y) + abs(z - p.z));
    }
}p[MAXN];

struct edge{
    int u, v, w;
}e[MAXM];

void addedge(int u, int v, int w) {
    e[cnt].u = u;
    e[cnt].v = v;
    e[cnt++].w = w;
}

int zl(int rt, int n, int m) {
    int ans = 0;
    int v;
    while (1) {
        for (int i = 0; i < n; i++) in[i] = INF;
        for (int i = 0; i < m; i++) {
            if (e[i].u != e[i].v && e[i].w < in[e[i].v]) {
                pre[e[i].v] = e[i].u;
                in[e[i].v] = e[i].w;
            }
        }
        for(int i = 0;i < n;i++)
            if(i != rt && in[i] == INF)
                return -1;
        int tn = 0;
        memset(id, -1, sizeof(id));
        memset(vis, -1, sizeof(vis));
        in[rt] = 0;
        for (int i = 0; i < n; i++) {
            ans += in[i];
            v = i;
            while (vis[v] != i && id[v] == -1 && v != rt) {
                vis[v] = i;
                v = pre[v];
            }
            if (v != rt && id[v] == -1) {
                for (int u = pre[v]; u != v; u = pre[u]) {
                    id[u] = tn;
                }
                id[v] = tn++;
            }
        }
        if (tn == 0) break;
        for (int i = 0; i < n; i++) {
            if (id[i] == -1) id[i] = tn++;
        }
        for (int i = 0; i < m;) {
            v = e[i].v;
            e[i].u = id[e[i].u];
            e[i].v = id[e[i].v];
            if (e[i].u != e[i].v) {
                e[i++].w -= in[v];
            } else {
               swap(e[i], e[--m]);
            }
        }
        n = tn;
        rt = id[rt];
    }
    return ans;
}

int main() {
    //freopen("in.txt", "r", stdin);
    int n, m, v, a, b, c;
    while (scanf("%d%d%d%d", &n, &a, &b, &c) != EOF) {
        if (n == 0) break;
        for (int i = 1; i <= n; i++) {
            scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);
        }

        cnt = 0;

        for (int u = 1; u <= n; u++) {
            scanf("%d", &m);
            for (int j = 0; j < m; j++) {
                scanf("%d", &v);
                if (v == u) continue;
                if (p[v].z <= p[u].z)
                    addedge(u, v, b * p[u].dis(p[v]));
                else
                    addedge(u, v, c + b * p[u].dis(p[v]));
            }
        }
        for (int v = 1; v <= n; v++) {
            addedge(0, v, p[v].z * a);
        }
        int ans = zl(0, n+1, cnt);
        printf("%d\n", ans);
    }
    return 0;
}