HDU - 4009:http://acm.hdu.edu.cn/showproblem.php?pid=4009

题意:

    有n户人家住在山上,现在每户人家(x,y,z)都要解决供水的问题,他可以自己挖井,也可以从特定的别人那里调水。问所有人家都接上水后最小的花费。

思路:

    据说是一道最小生成树的模版题,我觉得在建图上还是比较难的。每个人家从别人那里调水的关系是明确的,直接建图就行。那自己挖井,我们可以建立一个虚拟的源点,向每个点连一条边,边的权值就是挖井所要的费用。建完图后,就可以跑一遍最小树形图了。显然答案是一定存在的;

#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert> using namespace std;
//#pragma GCC optimize(3)
//#pragma comment(linker, "/STACK:102400000,102400000") //c++
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue typedef long long ll;
typedef unsigned long long ull; typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3; //priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl '\n' #define OKC ios::sync_with_stdio(false);cin.tie(0)
#define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行
#define REP(i , j , k) for(int i = j ; i < k ; ++i)
//priority_queue<int ,vector<int>, greater<int> >que; const ll mos = 0x7FFFFFFF; //
const ll nmos = 0x80000000; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //
const int mod = ;
const double esp = 1e-;
const double PI=acos(-1.0); template<typename T>
inline T read(T&x){
x=;int f=;char ch=getchar();
while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x=f?-x:x;
} /*-----------------------showtime----------------------*/
const int maxm = 1e6+;
const int maxn = 1e3+;
struct edge
{
int from,to,c;
}e[maxm];
int X,Y,Z,n,tot;
struct node
{
int x,y,z;
}p[maxn];
int in[maxn],vis[maxn],pre[maxn],id[maxn];
int rtt;
int zhuliu(int root,int n,int m){
int res = ;
while(true){
memset(in, inf, sizeof(in));
for(int i=; i<=m ;i++){
if(e[i].from != e[i].to && e[i].c < in[e[i].to]){
pre[e[i].to] = e[i].from;
in[e[i].to] = e[i].c;
}
}
for(int i=; i<=n; i++){
if(i!=root && in[i] == inf)
return -;
}
int tn = ,v;
memset(id,-,sizeof(id));
memset(vis,-,sizeof(vis));
in[root] = ;
for(int i=; i<=n; i++){
res += in[i];
v = i;
while(v!=root && id[v] == - && vis[v] != i){
vis[v] = i;
v = pre[v];
}
if(v!=root && id[v] == -){
id[v] = ++tn;
for(int u = pre[v] ; u!=v; u = pre[u]){
id[u] = tn;
}
}
}
if(tn == )break;
for(int i=; i<=n; i++){
if(id[i] == -)id[i] = ++tn;
} for(int i=; i<=m; i++){
int v = e[i].to;
e[i].to = id[e[i].to];
e[i].from = id[e[i].from];
if(e[i].to != e[i].from){
e[i].c -= in[v];
}
}
n = tn;root = id[root];
}
return res;
}
int get(int u,int v){
int ans = abs(p[u].x - p[v].x) +abs(p[u].y - p[v].y)+abs(p[u].z - p[v].z);
ans = ans * Y;
if(p[v].z > p[u].z)ans += Z;
return ans;
}
int main(){
while(~scanf("%d%d%d%d", &n, &X,&Y,&Z) && n+X+Y+Z){
tot = ;
for(int i=; i<=n; i++){
scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);
}
for(int i=; i<=n; i++){
int x,k;scanf("%d", &k);
for(int j=; j<=k; j++)
{
scanf("%d", &x);
e[++tot].from = i;
e[tot].to = x;
e[tot].c = get(i,x);
}
} for(int i=; i<=n; i++){
e[++tot].from = ;
e[tot].to = i;
e[tot].c = X * p[i].z;
} int ans = zhuliu(,n,tot);
printf("%d\n", ans);
}
return ;
}

HDU - 4009

最新文章

  1. select 选择的制作
  2. 使用Gson转换json数据为Java对象的一个例子
  3. html画布
  4. Eclipse添加代码注释模板
  5. linux内核调优详解
  6. Java中的可变参数以及foreach语句
  7. 通过fileupload上传文件超出大小
  8. 红领:挺进高端 青岛财经日报-htmlmainVerName
  9. HttpRuntime类
  10. HDoj-1527-取石子游戏
  11. c# 多线程 创建对象实例
  12. 算法 排序NB二人组 堆排序 归并排序
  13. SpringBoot(七):集成DataSource 与 Druid监控配置
  14. Mybateis mapper 接口 example 用法
  15. leetcode105
  16. Sql 查询结果 根据某个字段值 变更另外一个字段值 case when
  17. linux驱动编写之中断处理
  18. python调用修改变量新方法
  19. VMware虚拟机上配置nginx后,本机无法访问问题(转载)
  20. iis 应用程序预热

热门文章

  1. the license has been canceled
  2. win10安装.NET Framework 3.5方法
  3. LinkedHashMap的特殊之处
  4. 统计学习方法6—logistic回归和最大熵模型
  5. css3系列之详解perspective
  6. CTF杂项题解题思路
  7. Transformations 方块转换 USACO 模拟 数组 数学 耐心
  8. 教老婆学Linux运维(一)初识Linux
  9. U盘重装MacOS-Sierra系统
  10. hive explode 行拆列