BZOJ 1196 二分+Kruskal

2019-11-06 07:29:20

字体：大中小

来源：转载

供稿：网友

思路：二分答案判一下能不能加

//By SirisuRen#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=40050;int n,m,k,xx,yy,aa,bb,ans,f[N],top;struct Node{ int from,to,type,wei;Node(){} Node(int FR,int TO,int TY,int WE){ from=FR,to=TO,type=TY,wei=WE; }}node[N];bool cmp(Node a,Node b){return a.wei<b.wei;}int find(int x){return x==f[x]?x:f[x]=find(f[x]);}bool check(int mid){ int cnt1=0; for(int i=1;i<=n;i++)f[i]=i; for(int i=1;i<=mid;i++){ if(node[i].type!=1)continue; int fx=find(node[i].from),fy=find(node[i].to); if(fx!=fy)f[fx]=fy,cnt1++; } if(cnt1<k)return 0; for(int i=1;i<=mid;i++){ if(node[i].type==1)continue; int fx=find(node[i].from),fy=find(node[i].to); if(fx!=fy)f[fx]=fy,cnt1++; }return cnt1==n-1;}int main(){ scanf("%d%d%d",&n,&k,&m); for(int i=1;i<m;i++){ scanf("%d%d%d%d",&xx,&yy,&aa,&bb); node[++top]=Node(xx,yy,1,aa); node[++top]=Node(xx,yy,2,bb); } sort(node+1,node+1+top,cmp); int l=n-1,r=top; while(l<=r){ int mid=(l+r)>>1; if(check(mid))ans=mid,r=mid-1; else l=mid+1; } PRintf("%d/n",node[ans].wei);}

上一篇：九度oj1166

下一篇：玲珑杯 1100 萌萌哒的第五题（KMP+DP）