2024年天梯成信小赛--L2-3,L2-4补题

L2-3:Gwen的小剪刀

题意:

思路：二分美感度+克鲁斯卡尔

int n,m,sum0;
typedef struct myp{
    int u,v;
    int b,h;
};
bool cmp(myp a,myp b){
    return a.h<b.h;
}
myp arr[200005];
int fa[100005];
int find(int x){
//	if(x==fa[x]) return x;
//	return fa[x]=find(fa[x]);
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
void Union(int x,int y){
    int fa1=find(x),fa2=find(y);
    fa[fa1]=fa2;
}
bool check(int x){
    sum0=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    int cnt=1;
    for(int i=1;i<=m;i++){
        if(arr[i].b>=x&&find(arr[i].u)!=find(arr[i].v)){
            Union(arr[i].u,arr[i].v);
            sum0+=arr[i].h;
            cnt++;
        }
    }
    if(cnt==n) return true;
    else return false;
}
void solve(){           //补l2-3 Gwen的小剪刀--二分+最小生成树
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>arr[i].u>>arr[i].v>>arr[i].b>>arr[i].h;
    //sort(arr+1,arr+n+1,cmp);  //??????????逆天
    sort(arr+1,arr+m+1,cmp);
    int ans1=1,ans2=INT_MAX;
    int l=1,r=1e9+1;            //二分美观度
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            ans1=max(ans1,mid);
            ans2=sum0;   //!!!!!不能取ans2=min(ans2,sum0)!!!!!!!
            l=mid+1;
        }
        else r=mid-1;
    }
    cout<<ans1<<endl<<ans2;
}

ps:逆天排序范围写错了。。还有ans2-快乐值是不能取min的，在美感度x合法的情况下，算出来的即是最小的ans2。否则取了min会导致ans2对应的美感度不对。

 L2-3:超时空之恋

题意：