|BZOJ 2429|生成树|[HAOI2006]聪明的猴子

2019-11-06 07:46:58

字体：大中小

来源：转载

供稿：网友

BZOJ传送门最小瓶颈路，求一条路径，使得u−>v $u->v$ 路径上的最大边权最小。可以知道，最小瓶颈路必在最小生成树上，所以用最小生成树求解求出最小的最大边权后和每个猴子的距离比较即可 (PS: 之前还用dfs跑。。结果发现直接比较即可。。)

/* Date: 04-03-17 10:27 bzoj 2429*/#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<vector>#define ms(i,j) memset(i,j,sizeof i);using namespace std;const int MAXM = 500 + 5, MAXN = 1000 + 5;struct edge{ int u; int v; double w; bool Operator < (const edge &b) const { return w < b.w; }}e[MAXN*MAXN];int en = 0;void addE(int x, int y, double w){ en++; e[en].u = x; e[en].v = y; e[en].w = w;}int fa[MAXN];int find(int x) {return (fa[x]==x) ? (x) : (fa[x] = find(fa[x]));}int m, n;int h[MAXM];int x[MAXN], y[MAXN];int main(){ scanf("%d", &m); for (int i=1;i<=m;i++) { scanf("%d", &h[i]); } scanf("%d", &n); for (int i=1;i<=n;i++) { scanf("%d%d", &x[i], &y[i]); fa[i] = i; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i!=j) { addE(i, j, sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) ) ); } sort(e+1, e+1+en); int tot = 0; double maxe = 0; for (int i=1;i<=en;i++) { int fx = find(e[i].u); int fy = find(e[i].v); if (fx==fy) continue; fa[fx] = fy; tot++; if (tot == n-1) {maxe = e[i].w; break;} } int ans = 0; for (int i=1;i<=m;i++) { if (h[i]>=maxe) ans++; } PRintf("%d/n", ans); return 0;}

上一篇：城市交通

下一篇：C#文件操作