[BZOJ 2429]聪明的猴子
转载请注明出处：http://danihao123.is-programmer.com/
图论填坑中……
这题不难，直接造图搞MST（严格讲是最小瓶颈生成树）即可。比较感人的是，Kruskal竟然也能过……
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | /************************************************************** Problem: 2429 User: danihao123 Language: C++ Result: Accepted Time:320 ms Memory:12592 kb****************************************************************/ #include <cstdio>#include <algorithm>#include <cmath>using namespace std;const int maxn=1001,maxm=501;int n;struct Edge{ int u,v,d; bool operator < (const Edge& x) const{ return d<x.d; }}; // DJoinst Setint p[maxn],rank[maxn];int find_set(int x){ if(p[x]==x) return x; else return p[x]=find_set(p[x]);}void link_set(int x,int y){ if(rank[x]>rank[y]){ p[y]=x; }else{ p[x]=y; if(rank[x]==rank[y]) rank[y]++; }}inline void union_set(int x,int y){ link_set(find_set(x),find_set(y));}inline bool is_same(int x,int y){ return find_set(x)==find_set(y);}inline void init_set(){ for(register int i=1;i<=n;i++) p[i]=i; // memset(rank,0,sizeof(rank));} // Kruskalint m=0;Edge E[maxn*maxn];int MST(){ register int i,ans,count=0; init_set(); sort(E,E+m); for(i=0;i<m && count<=(n-1);i++){ if(!is_same(E[i].u,E[i].v)){ union_set(E[i].u,E[i].v); ans=E[i].d; count++; } } return ans;} int MK[maxm],Tree[maxn][2];int main(){ int monkey; register int i,j,sd,ans=0; scanf("%d",&monkey); for(i=1;i<=monkey;i++) scanf("%d",&MK[i]); scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d%d",&Tree[i][0],&Tree[i][1]); for(i=1;i<=n;i++){ for(j=i+1;j<=n;j++){ E[m].u=i; E[m].v=j; E[m].d=hypot(abs(Tree[i][0]-Tree[j][0]),abs(Tree[i][1]-Tree[j][1])); m++; } } sd=MST(); for(i=1;i<=monkey;i++) if(MK[i]>=sd) ans++; printf("%d\n",ans); return 0;} |
大约 1 年前
Dedicated news coverage of latest happenings around the country Our team comprises of professional writers & citizen journalists with diverse range of interest in Journalism who are passionate about publishing the Education Updates with transparency in general 12thmodelquestionspapers.in public interest is a initiative of professional writers who have come together for dedicated news coverage of latest happenings around the country (India). Our team comprises of professional writers & citizen journalists with diverse range of interest in Journalism