[BZOJ 2429]聪明的猴子
图论填坑中……
这题不难,直接造图搞MST(严格讲是最小瓶颈生成树)即可。比较感人的是,Kruskal竟然也能过……
代码:
/************************************************************** 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 Set int 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)); } // Kruskal int 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; }
[BZOJ 1682]干草危机
这道题就是求最小瓶颈生成树中边的最大值。
然而图的MST就是图的一个最小瓶颈生成树……这下问题就迎刃而解了。
代码:
/************************************************************** Problem: 1682 User: danihao123 Language: C++ Result: Accepted Time:44 ms Memory:940 kb ****************************************************************/ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define REP(i,n) for(i=0;i<n;i++) #define REPB(i,n) for(i=1;i<=n;i++) #define FROMG_TO E[i].u,E[i].v const int maxn=2001,maxm=10001; int n,m; // Djoint set int 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(){ register int i; for(i=1;i<=n;i++) p[i]=i; // memset(rank,0,sizeof(rank)); } // Graph struct Edge{ int u,v,d; }; int cmp(const Edge& a,const Edge& b){ return a.d<b.d; } Edge E[maxm]; int mst(){ register int i,cnt=0,ans=0; init_set(); sort(E,E+m,cmp); for(i=0;cnt<(n-1) && i<m;i++){ if(!is_same(FROMG_TO)){ union_set(FROMG_TO); ans=max(ans,E[i].d); cnt++; } } return ans; } int main(){ register int i; scanf("%d%d",&n,&m); REP(i,m){ scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d); } printf("%d\n",mst()); return 0; }