不是很理解这题为什么要二分
  • 板块P2798 爆弹虐场
  • 楼主jikky
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/10/10 19:58
  • 上次更新2024/10/10 21:46:29
查看原帖
不是很理解这题为什么要二分
1382982
jikky楼主2024/10/10 19:58

自己写的并查集只AC了点一,求各位大佬帮忙看看

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct E{
	int u;
	int v;
	int w;
	bool vel;
}e[N];
int tot=0;
int fa[N];
void add(int u,int v,int w,int c){
	e[++tot].u=u;
	e[tot].v=v;
	e[tot].w=w;
	e[tot].vel=c;
}

bool cmp(E a,E b){
	return a.w<b.w;
}

int find(int k){
	if(fa[k]==k){
		return fa[k];
	}
	else{
		fa[k]=find(fa[k]);
		return fa[k];
	}
}

int main(){
	int n,k,m;
	cin>>n>>k>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		int t1,t2;
		cin>>u>>v>>t1>>t2;
		add(u,v,t1,1);
		add(u,v,t2,0);
	}
	int cnt=0;
	sort(e+1,e+tot+1,cmp);
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	int p=1;
	for(int i=1;i<=2*m;i++){
		fa[1]=find(1);
		while(find(p)==find(1)&&p<=n){
			p++;
		}
		if(e[i].vel){
			cnt++;
		}
		int u=e[i].u;
		int v=e[i].v;
		fa[u]=find(u);
		fa[v]=find(v);
		fa[find(u)]=fa[v];
		if(cnt>=k&&p==n+1){
			cout<<e[i].w;
			return 0;
		}
	}
	return 0;
}
2024/10/10 19:58
加载中...