题目链接
基本算法
最小树形图基于贪心和缩点的思想。
1. 求最短弧集合E0
从所有以vi 为终点的弧中取一条最短的，若对于vi ，没有入边，则不存在最小树形图，算法结束;如果能取，则得到有n个点和n-1条边组成的图G 的一个子图G′ ，该子图的权值一定是的最小的，但是不一定是一棵树。
2. 检查E0
若E0 没有有向环且不含收缩点，则计算结束，E0 就是以G 的v0 为根的最小树形图。若E0 没有有向环，但含收缩点，则转步骤（4），若E0 含有有向环C，则转入步骤（3）。
3. 收缩G 的C收缩成点u，对于图G 中两端都属于C的边的都被收缩掉了，其它弧仍保留，得到一个新的图G1 ,G1 中以收缩点为终点的弧的长度都要变化，变化的规律是：设点v 在环C中，且环中指向v 的边长为w，点v′ 不在环C中，则对于每一条边<v,v′> ,在G1 中有边<v′,u> 与其对应，且权值W(G1)(<v′,u>)=WG(<v′,v>)−w 。对于图G 中以环C为C的起点的边<v′,v> , 在图中G1 有边<u,v′> ，则W(G1)(<u,v′>)=WG(<v,v′>) 。
4. 展开缩点。
题意
每个家庭挖水井需要花费z*X, 如果挖水渠就是地势高的家庭到地势低的曼哈顿距离乘以Y,若是低到高在加Z。最后求最小花费。
解析
建图的最难处理的就是那个，自己挖水井。建立一个源点，和每个点建边，权值为在z*X，剩下的就根据关系建边即可。最后求有向图的最小树形图即可。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn = 1000+100;
int dfn[maxn], low[maxn];
int st[maxn];
int stk = 0;
struct node {
int u, v, w;
node ()
{}
node (int _u, int _v, int _w) {
u = _u;
v = _v;
w = _w;
}
}e[maxn*maxn];
int dep = 0, bcc_cnt;
int in[maxn], vis[maxn], id[maxn], pre[maxn];
vector<int>g[maxn];
struct point {
int x, y, z;
point(){}
}p[maxn];
int dis(point a, point b) {
return abs(a.x-b.x)+abs(a.y-b.y)+abs(a.z-b.z);
}
int Directed_MST(int root, int n, int m) {
int ret = 0;
while (1) {
//第一步：找到入边最小边
for (int i=0; i<n; i++)
in[i] = INF;
for (int i=0; i<m; i++) {
int u = e[i].u, v = e[i].v;
if (e[i].w < in[v] && u != v) {
in[v] = e[i].w;
pre[v] = u;
}
}
for (int i=0; i<n; i++) { //没有入边，就不会产生最小树形图
if (i == root)
continue;
if (in[i] == INF)
return -1;
}
int cntnode = 0;
memset(id, -1, sizeof(id));
memset(vis, -1, sizeof(vis));
// 第二步：找环
in[root] = 0;
for (int i=0; i<n; i++) {
ret += in[i];
int v = i;
while (vis[v] != i && id[v] == -1 && v != root) {
vis[v] = i;
v = pre[v];
}
if (v != root && id[v] == -1) {
for (int u=pre[v]; u!=v; u=pre[u])
id[u] = cntnode;
id[v] = cntnode++;
}
}
if (cntnode == 0)
break;
for (int i=0; i<n; i++) {
if (id[i] == -1)
id[i] = cntnode++;
}
//第三步：缩点、重新标记
for (int i=0; i<m; i++) {
int 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];
}
n = cntnode;
root = id[root];
}
return ret;
}
int main() {
int n, X, Y, Z;
while (~scanf("%d%d%d%d", &n, &X, &Y, &Z) && n) {
int S = 0;
int m = 0;
for (int i=1; i<=n; i++) {
scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);
e[m++] = node(S, i, p[i].z*X);
g[S].push_back(i);
}
for (int i=1; i<=n; i++) {
int k;
scanf("%d", &k);
int u = i;
while (k--) {
int v;
scanf("%d", &v);
if (v == i)
continue;
int w = dis(p[u], p[v])*Y;
if (p[u].z < p[v].z)
w += Z;
e[m++] = node (u, v, w);
}
}
int ans = Directed_MST(0, n+1, m);
printf("%d\n", ans);
}
return 0;
}