烟台网站建设网站推广,导购网站一站式建站,工厂管理软件,贵州百度推广优化报告一. 题目
题目描述 输入输出格式 样例
样例1 样例2 样例解释 数据范围 二. 思路
对于前20%数据 解法
因为保证了 x i 1 x_i 1 xi1#xff0c;也就是说这些点都在 x 1 x 1 x1 这条直线上。
那么最优解必定是在 c i c_i ci 最小的点上建发电站#xff0c…一. 题目
题目描述 输入输出格式 样例
样例1 样例2 样例解释 数据范围 二. 思路
对于前20%数据 解法
因为保证了 x i 1 x_i 1 xi1也就是说这些点都在 x 1 x 1 x1 这条直线上。
那么最优解必定是在 c i c_i ci 最小的点上建发电站然后把这些点之间全部联通即可。
即最终答案 a n s min 1 ≤ i ≤ n c i max 1 ≤ i ≤ n y i − min 1 ≤ i ≤ n y i ans \min_{1 \leq i \leq n}c_i \max_{1 \leq i \leq n}y_i - \min_{1 \leq i \leq n} y_i ans1≤i≤nminci1≤i≤nmaxyi−1≤i≤nminyi
可见我们要枚举 1 1 1 到 n n n 所以时间复杂度为 O ( n ) O(n) O(n) 。
对于前70%数据 解法
思路分析
因为50%的数据没有什么特殊的地方至少作者没有想到所以直接从70%的数据入手。
思考 k i 1 k_i 1 ki1 也就是点之间的连线每条边的单位花费为 1 1 2 112 112 而 1 0 8 ≤ c i ≤ 1 0 9 10^8 \leq c_i \leq 10^9 108≤ci≤109 很大并且在 n ≤ 2000 n \leq 2000 n≤2000 的情况下我们发现连线的花费往往小于构建发电站的花费。所以容易得出贪心策略在 c i c_i ci 最小的点建发电站其他点都与这个点联通。
这个问题就等价于要把图上的每一个点都联通并且花费最小。
先考虑如何联通每一个点构建一棵树共有 n n n 个点和 n − 1 n-1 n−1 条边。
其次要让花费小这不就是最小生成树吗
具体实现
我们先把 n n n 个点之间两两连线每条边的权值为该边的花费构建一个完全图然后对这张图 跑Kruskal或Prim最小生成树 即可。
对于100%数据 解法
发现100%的数据与70%的数据对比 k i k_i ki 与 c i c_i ci 的取值范围更广泛所以不一定只有一个发电站是最优解。
那么按照70%数据的思路我们对于每一个发电站都会构建出一棵最小生成树但一棵不一定涵盖所有点。即这张图变成了一个最小生成树组成的森林。
这样的话我们没法枚举每个发电站再构建最小生成树。能不能把这些树合在一起呢
这里我们引入 “虚拟点思想”也叫做 “超级零点” 。也就是新增0号或不在范围内的点并把它向其他点都连一条边边的权值为在与其相连的点构建发电站的花费。
这样我们就可以对这个图跑最小生成树即可。因为最小生成树一定会连向虚拟点所以至少会构建一个发电站思路可行。
三. 代码实现
20pts 解法
#include bits/stdc.h
using namespace std;
const int N 2055;
long long id,n,k[N],x[N],y[N],maxx,minn1e17,ress1e17;
long long c[N],f[N],res 1e17,ans 0,cnt;
struct node
{long long u,v,w;
}a[N*N*2];
int main()
{freopen(electricity.in,r,stdin);freopen(electricity.out,w,stdout);cin id;cin n;for (int i1;in;i){scanf(%lld%lld,x[i],y[i]);}for (int i1;in;i){scanf(%lld,c[i]);}for (int i1;in;i){scanf(%lld,k[i]);}if (1 id id 4){for (int i1;in;i){maxx max(maxx,y[i]);minn min(minn,y[i]);ress min(ress,c[i]);}cout(maxx-minn)*2ress;return 0;}return 0;
}70pts 解法
#include bits/stdc.h
using namespace std;
const int N 2005;
long long id,n,k[N],x[N],y[N],maxx,minn1e17,ress1e17;
long long c[N],f[N],res 1e17,ans 1e17,cnt;
struct node
{long long u,v,w;
}a[N*N];
long long zabs(long long s)
{if (s 0) return s;return -s;
}
long long dis(long long a,long long b)
{return zabs(x[a]-x[b])zabs(y[a]-y[b]);
}
void add(long long h,long long b,long long c)
{a[cnt].u h;a[cnt].v b;a[cnt].w c;
}
bool cmp(node x,node y)
{return x.w y.w;
}
long long fnd(int x)
{if (x f[x]) return x;return f[x] fnd(f[x]);
}
int main()
{freopen(electricity.in,r,stdin);freopen(electricity.out,w,stdout);cin id;cin n;for (int i1;in;i){scanf(%lld%lld,x[i],y[i]);}for (int i1;in;i){scanf(%lld,c[i]);}for (int i1;in;i){scanf(%lld,k[i]);}ans 1e17;for (int i1;in;i){ans mins(ans,c[i]);}for (int i1;in;i){for (int ji1;jn;j){add(j,i,dis(i,j)*(k[i]k[j]));add(i,j,dis(i,j)*(k[i]k[j]));}}sort(a1,acnt1,cmp);long long tot 0;for (int j1;jn;j){f[j] j;}for (int j1;jcnt;j){long long p1 fnd(f[a[j].u]);long long p2 fnd(f[a[j].v]);if (f[p1] f[p2]) continue;f[p1] fnd(f[p2]);ans a[j].w;tot;if (tot1 n) break;}coutans;return 0;
}100pts 解法
#include bits/stdc.h
using namespace std;
const int N 2055;
long long id,n,k[N],x[N],y[N],maxx,minn1e17,ress1e17;
long long c[N],f[N],res 1e17,ans 0,cnt;
struct node
{long long u,v,w;
}a[N*N*2];
long long zabs(long long s)
{if (s 0) return s;return -s;
}
long long dis(long long a,long long b)
{return zabs(x[a]-x[b])zabs(y[a]-y[b]);
}
void add(long long h,long long b,long long c)
{a[cnt].u h;a[cnt].v b;a[cnt].w c;
}
bool cmp(node x,node y)
{return x.w y.w;
}
long long fnd(int x)
{if (x f[x]) return x;return f[x] fnd(f[x]);
}
int main()
{freopen(electricity.in,r,stdin);freopen(electricity.out,w,stdout);cin id;cin n;for (int i1;in;i){scanf(%lld%lld,x[i],y[i]);}for (int i1;in;i){scanf(%lld,c[i]);}for (int i1;in;i){scanf(%lld,k[i]);}ans 0;//构图for (int i1;in;i){for (int ji1;jn;j){add(j,i,dis(i,j)*(k[i]k[j]));add(i,j,dis(i,j)*(k[i]k[j]));}}//虚拟点构建for (int i1;in;i){add(n1,i,c[i]);add(i,n1,c[i]);}sort(a1,acnt1,cmp);long long tot 0;for (int j1;jn1;j){f[j] j;}//Kruskal最小生成树for (int j1;jcnt;j){long long p1 fnd(f[a[j].u]);long long p2 fnd(f[a[j].v]);if (f[p1] f[p2]) continue;f[p1] fnd(f[p2]);ans a[j].w;tot;if (tot n) break;}coutans;return 0;
}四. 总结
这道图论题在CSP-J模拟赛放了T3感觉略难最小生成树和虚拟点思想略有超纲但不引进“虚拟点思想”的70分给的很足。总体来说是一道练习最小生成树和虚拟点思想的好题。
