销售员做网站,深圳餐饮设计公司排名,php网站优点,百度网站建设多钱P2847 [USACO16DEC] Moocast G
[USACO16DEC] Moocast G
题面翻译
Farmer John 的 N N N 头牛 ( 1 ≤ N ≤ 1000 1 \leq N \leq 1000 1≤N≤1000) 为了在他们之间传播信息#xff0c;想要组织一个哞哞广播系统。奶牛们决定去用步话机装备自己而不是在很远的距离…P2847 [USACO16DEC] Moocast G
[USACO16DEC] Moocast G
题面翻译
Farmer John 的 N N N 头牛 ( 1 ≤ N ≤ 1000 1 \leq N \leq 1000 1≤N≤1000) 为了在他们之间传播信息想要组织一个哞哞广播系统。奶牛们决定去用步话机装备自己而不是在很远的距离之外互相哞哞叫所以每一头奶牛都必须有一个步话机。这些步话机都有一个限制传播半径但是奶牛们可以间接地通过中间奶牛传播信息所以并不是每头牛都必须直接向其他每一头奶牛连边。
奶牛们需要去决定多少钱花在步话机上如果他们花了 X X X, 那么他们都将会得到 X \sqrt{X} X 距离的步话机。所以两头牛之间的欧几里得距离平方最多是 X X X。请帮助奶牛们找到最小的 X X X 使得图是强连通的。
题目描述
Farmer John’s N N N cows ( 1 ≤ N ≤ 1000 1 \leq N \leq 1000 1≤N≤1000) want to organize an emergency “moo-cast” system for broadcasting important messages among themselves.
Instead of mooing at each-other over long distances, the cows decide to equip themselves with walkie-talkies, one for each cow. These walkie-talkies each have a limited transmission radius, but cows can relay messages to one-another along a path consisting of several hops, so it is not necessary for every cow to be able to transmit directly to every other cow.
The cows need to decide how much money to spend on their walkie-talkies. If they spend X X X, they will each get a walkie-talkie capable of transmitting up to a distance of X \sqrt{X} X . That is, the squared distance between two cows must be at most X X X for them to be able to communicate.
Please help the cows determine the minimum integer value of X X X such that a broadcast from any cow will ultimately be able to reach every other cow.
输入格式
The first line of input contains N N N.
The next N N N lines each contain the x x x and y y y coordinates of a single cow. These are both integers in the range 0 … 25 , 000 0 \ldots 25,000 0…25,000.
输出格式
Write a single line of output containing the integer X X X giving the minimum amount the cows must spend on walkie-talkies.
样例 #1
样例输入 #1
4
1 3
5 4
7 2
6 1样例输出 #1
17提示
没有提示
题解
根本用不着二分答案嘛。直接 N 2 N^2 N2建边跑一遍Kruskal。记录在最小生成树中的最长的一条边。显然只要使得这条边能够建立那么这棵最小生成树中的所有的边都可以建立。答案就是最长的边的距离的平方注意要用 d o u b l e double double存边权。
#include iostream
#include cstdio
#include cstring
#include algorithm
#include cmathusing namespace std;const int maxn 1e33;
int n, x[maxn], y[maxn], cnt, tot, f[maxn];
double Ans;
struct Edge{int u, v;double w;
}ed[maxn * maxn];
inline bool cmp(Edge a, Edge b){return a.w b.w;
}
inline int find(int x){if(x f[x]) return x;else return f[x] find(f[x]);
}
inline void Kruskal(){for(int i1; in; i) f[i] i;for(int i1; in; i){for(int j1; jn; j){if(i ! j){cnt;ed[cnt].u i, ed[cnt].v j, ed[cnt].w sqrt((x[i]-x[j])*(x[i]-x[j])(y[i]-y[j])*(y[i]-y[j]));}}}sort(ed1, ed1cnt, cmp);for(int i1; icnt; i){int xx find(ed[i].u), yy find(ed[i].v);if(xx ! yy){f[xx] find(yy);tot ;Ans ed[i].w;}if(tot n-1){break;}}
}int main(int argc, const char * argv[]){scanf(%d, n);for(int i1; in; i){scanf(%d%d, x[i], y[i]);}Kruskal();printf(%.0lf, Ans * Ans);
}
//Written by Kevin ☑当然,最小生成树才是这道题的最优解
为什么呢大家应该都学过勾股定理吧在平面直角坐标系中两点A(x1,y1),B(x2,y2)的距离|AB|等于 s q r t ( ( x 1 − x 2 ) 2 ( y 1 − y 2 ) 2 sqrt((x1-x2)^2(y1-y2)^2 sqrt((x1−x2)2(y1−y2)2而我们可以发现我们最后要求的是最大的 ∣ A B ∣ 2 |AB|^2 ∣AB∣2,也就是 ( x 1 − x 2 ) 2 ( y 1 − y 2 ) 2 (x1-x2)^2(y1-y2)^2 (x1−x2)2(y1−y2)2当然在C里得写成(x1-x2) * (x1-x2)(y1-y2) * (y1-y2))所以我们只要求出边权为两点距离平方的最小生成树中最长边的长就可以了。
首先我们可以通过一次双重循环求出每条边的边权然后再跑一边最小生成树算法。
被熟知的求最小生成树的算法有prime、kruskal两种而这次我们的图是完全图即图的每两点之间都有连边而prime更适合跑稠密图因此我们选用prime算法。
#includebits/stdc.h
using namespace std;
long long n,i,j,x[1001],y[1001],p[1001][1001],d[1001],u,max1;
bool b[1001];
priority_queuepairlong long,long long q;//堆优化
int main(int argc, const char * argv[]){scanf(%lld,n);for (i1;in;i)scanf(%lld%lld,x[i],y[i]);for (i1;in;i)for (j1;jn;j)p[i][j](x[i]-x[j])*(x[i]-x[j])(y[i]-y[j])*(y[i]-y[j]);//求出两两点之间的距离for (i1;in;i) d[i]1e11;d[1]0;max10;q.push(make_pair(0,1));while (q.size()){uq.top().second;q.pop();if (b[u]) continue;max1max(max1,d[u]);//求出最大边权b[u]true;for (i1;in;i)if (d[i]p[u][i]){d[i]p[u][i];q.push(make_pair(-d[i],i));//prime}}printf(%lld,max1);return 0;
}
//Written by Kevin ☑︎
