[BZOJ 1196]公路修建问题
转载请注明出处：http://danihao123.is-programmer.com/
挺简单的二分答案题……然而到现在才A
思路很明显，直接二分最终答案。那么判定如何做呢？
假设判定谓词为，那么我们首先考虑选白边。贪心加入边权小于
的边（当然是否有必要就要用并查集判定了。并且这样就算加的超过了
条也不会对答案造成影响）。然后白边加的不够
谓词就是假了。
然后再考虑黑边，接下来的事情就很简单了。
代码：
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 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 | /************************************************************** Problem: 1196 User: danihao123 Language: C++ Result: Accepted Time:672 ms Memory:1212 kb****************************************************************/ #include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define REP(i,n) for(i=0;i<(n);i++)#define RAP(i,n) for(i=1;i<=(n);i++)const int maxn=10001,maxm=20001; struct Edge{ int u,v,d1,d2;};bool cmp1(const Edge& x,const Edge& y){ return x.d1<y.d1;}bool cmp2(const Edge& x,const Edge& y){ return x.d2<y.d2;} int n;int p[maxn],rank[maxn];int find_set(int x){ if(p[x]==x) return x; else return p[x]=find_set(p[x]);}inline 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));} int k,m;Edge E[maxm];inline bool check(int x){ register int i,first_cnt=0,cnt=0; init_set(); sort(E,E+m,cmp1); REP(i,m){ if(E[i].d1>x){ break; }else{ if(!is_same(E[i].u,E[i].v)){ first_cnt++; cnt++; union_set(E[i].u,E[i].v); } } if(cnt==n-1){ return true; } } if(first_cnt<k) return false; sort(E,E+m,cmp2); REP(i,m){ if(E[i].d2>x){ break; }else{ if(!is_same(E[i].u,E[i].v)){ cnt++; union_set(E[i].u,E[i].v); } } if(cnt==n-1) return true; } return false;}int main(){ register int i,L=1,M,R=0; scanf("%d%d%d",&n,&k,&m); m--; REP(i,m){ scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].d1,&E[i].d2); R=max(R,E[i].d1); } R++; while(L<R){ M=L+(R-L)/2; if(check(M)) R=M; else L=M+1; } printf("%d\n",L); return 0;} |
3 年前
Candidates can download NCERT Urdu Sample Paper 2023 Class 6 for all formats of exams held under Term-1& Term-2 such as SA1, NCERT Urdu Question Paper Class 6 SA2, FA1, FA2, FA3, FA4 and Assignment exams. Every student who wants to know the new exam scheme of question pattern or question paper style can download the NCERT STD-6 Ibtedai Sample Paper 2023 with sample answers to get complete details of the exam.Every student who wants to know the new exam scheme of question pattern or question paper style can download the NCERT STD-6 Ibtedai Sample Paper 2023 with sample answers to get complete details of the exam.