首页 > 代码库 > [HNOI乱草]
[HNOI乱草]
前言:
poi的想法题刷多了 想刷刷代码题 其他省的可能有点太难了 所以选了一个省开了个刀，嘻嘻`(*∩_∩*)′
| [HNOI2006]公路修建问题 |
一开始看错题了草
意思是花费最多的一条公路尽量少，求最大花费的边
语文老师有教过最大的最小 最小的最大 就是二分
二分最多的那一条公路 然后看看第一公路够不够 反正不管总花费 所以全部选第一条 然后再选第二条 然后用并查集看看连不连通就好 sb题
#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<set>#define Maxn 10010using namespace std;struct node{ int x,y,c;};bool Cmp(const node &x,const node &y){return x.c<y.c;}node S1[Maxn*2],S2[Maxn*2];int N,M,K; int fa[Maxn];inline int find(int x){if(x==fa[x]) return x; else return fa[x]=find(fa[x]);}inline int FindS1(int x){ int L=1,R=M; int ret=-1; while(L<=R) { int mid=(L+R)>>1; if(S1[mid].c<=x){L=mid+1; ret=mid;} else R=mid-1; } return ret;}inline int FindS2(int x){ int L=1,R=M; int ret=-1; while(L<=R) { int mid=(L+R)>>1; if(S2[mid].c<=x){L=mid+1; ret=mid;} else R=mid-1; } return ret;}int main(){ //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); scanf("%d%d%d",&N,&K,&M); for(int i=1;i<M;i++) { int x,y,c1,c2; scanf("%d%d%d%d",&x,&y,&c1,&c2); node x1; x1.x=x; x1.y=y; x1.c=c1; node x2; x2.x=x; x2.y=y; x2.c=c2; S1[i]=x1; S2[i]=x2; } sort(S1+1,S1+M+1,Cmp); sort(S2+1,S2+M+1,Cmp); int L=1; int R=30000; int ret=-1; while(L<=R) { int mid=(L+R)>>1; int it1=FindS1(mid); int it2=FindS2(mid); int it; if(it1<K){L=mid+1; continue;} else if(it1+it2<N-1){L=mid+1; continue;} for(int i=1;i<=N;i++) fa[i]=i; int sum=0; for(it=1;it<=it1;it++) { int xx=find(S1[it].x); int yy=find(S1[it].y); if(xx!=yy){sum++; fa[xx]=yy;} } if(sum<K){L=mid+1; continue;} for(it=1;it<=it2;it++) { int xx=find(S2[it].x); int yy=find(S2[it].y); if(xx!=yy){sum++; fa[xx]=yy;} } if(sum==N-1){ret=mid; R=mid-1; continue;} else {L=mid+1; continue;} } printf("%d\n",ret); return 0;}/*10 4 203 9 6 31 3 4 15 3 10 28 9 8 76 8 8 37 1 3 24 9 9 510 8 9 12 6 9 16 7 9 82 6 2 13 8 9 53 2 9 61 6 10 35 6 3 12 7 6 17 8 6 210 9 2 17 1 10 2*/
[HNOI乱草]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。