BZOJ 1196 二分+Kruskal


思路:

二分答案

判一下能不能加


//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);
}

0 個評論

要回覆文章請先登錄註冊