首页 > 代码库 > HDU - 4009 Transfer water(最小树形图)
HDU - 4009 Transfer water(最小树形图)
题目大意:有N个点。每一个点都有对应的三维坐标(x,y,z)
如今要求每一个点都能获得水,或者水的方式有两种
1.自己挖井,费用为X * 海拔高度z
2.铺设管道引水。
a.假设海拔高度小于引水处。费用为两地曼哈顿距离*Y
b.假设海拔高度大于饮水处。费用为两地曼哈顿距离*Y + Z
解题思路:设置一个虚根。虚根引向全部的点,权值为挖井的费用,接着依照要求连边,求出最小树形图就可以
#include <cstdio>
#include <cstring>
#define N 1010
#define abs(a) ((a)>0?(a):(-(a)))
struct Edge{
int u, v, c;
}E[N*N];
struct Point{
int x, y, z;
}P[N];
int n, x, y, z, tot;
void AddEdge(int u, int v, int c) {
E[tot].u = u; E[tot].v = v; E[tot++].c = c;
}
void init() {
tot = 0;
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &P[i].x, &P[i].y, &P[i].z);
AddEdge(0, i, P[i].z * x);
}
int k, t;
for (int i = 1; i <= n; i++) {
scanf("%d", &k);
while (k--) {
scanf("%d", &t);
if (t == i)
continue;
if (P[i].z >= P[t].z) {
int dis = abs(P[t].x - P[i].x) + abs(P[t].y - P[i].y) + abs(P[t].z - P[i].z);
AddEdge(i, t, dis * y);
}
else {
int dis = abs(P[t].x - P[i].x) + abs(P[t].y - P[i].y) + abs(P[t].z - P[i].z);
AddEdge(i, t, dis * y + z);
}
}
}
}
#define INF 0x3f3f3f3f
int in[N], pre[N], vis[N], id[N];
int Directed_MST(int root, int n) {
int ans = 0, u, v, tmp;
while (1) {
for (int i = 0; i < n; i++)
in[i] = INF;
for (int i = 0; i < tot; i++) {
u = E[i].u;
v = E[i].v;
if (u != v && E[i].c < in[v]) {
in[v] = E[i].c;
pre[v] = u;
}
}
memset(vis, -1, sizeof(vis));
memset(id, -1, sizeof(id));
in[root] = 0;
int subnode = 0;
for (int i = 0; i < n; i++) {
ans += in[i];
tmp = i;
while (vis[tmp] != i && tmp != root && id[tmp] == -1) {
vis[tmp] = i;
tmp = pre[tmp];
}
if (id[tmp] == -1 && tmp != root) {
u = pre[tmp];
while (u != tmp) {
id[u] = subnode;
u = pre[u];
}
id[tmp] = subnode++;
}
}
if (subnode == 0)
break;
for (int i = 0; i < n; i++)
if (!(~id[i]))
id[i] = subnode++;
for (int i = 0; i < tot; i++) {
tmp = 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].c -= in[tmp];
}
n = subnode;
root = id[root];
}
return ans;
}
void solve() {
n++;
int ans = Directed_MST(0,n);
if (ans == -1)
printf("poor XiaoA\n");
else
printf("%d\n", ans);
}
int main() {
while (scanf("%d%d%d%d", &n, &x, &y, &z) != EOF && n + x + y + z) {
init();
solve();
}
return 0;
}
HDU - 4009 Transfer water(最小树形图)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。