此博客停更

好久没写题解了……

题目描述：有N(1≤N≤2000)个节点，M(1≤M≤10000)条边。你要保留一些边，使得这个图连通且最大的边最小，输出最大边。

解题思路：→_→将边按权值从大到小排序，枚举从头开始删的边数~每次判一遍是否联通，感觉这样很对的说~，→_→理想中的最坏情况时间复杂度会到达O(NM)即遍历删几条边的复杂度*bfs复杂度，啊咧不会超啊→_→，不过我用的是更快的方法↓

解题思路2：二分答案+bfs，每次二分bfs判断图的联通性，于是时间复杂度就变成了 二分的复杂度*bfs的复杂度 ，所以总的复杂度是O(log(max(边权))M)。↓ 代码略丑

#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int n,m;
bool b[2000+10];
int f[2001][2001][2];
#define max(a,b) (a>b?a:b)

inline int read(){
    char ch;int a=0;bool f=false;
    ch=getchar();while((ch<'0'||ch>'9')&&(ch!='-'))ch=getchar();
    if(ch!='-')a*=10,a+=ch-'0';else f=true;
    while(((ch=getchar())>='0')&&(ch<='9'))a*=10,a+=ch-'0';
    if(f)a=-a;
    return a;
}

bool find(int mid){
	queue<int>Q;
	int k=1;
	memset(b,0,sizeof(b));
	Q.push(1);b[1]=1;
	while(!Q.empty()){
		int x=Q.front();
		for(int i=1;i<=f[x][0][0];i++){
			if((!b[f[x][i][0]])&&(f[x][i][1]<=mid))
				b[f[x][i][0]]=1,Q.push(f[x][i][0]),k++;
		}
		Q.pop();
		if(k==n)return 1;
	}
	return 0;
}

int main(){
	n=read(),m=read();
	int Max=0;
	for(int i=1;i<=m;i++){
		int x,y,z;
		x=read(),y=read(),z=read();
		f[x][++f[x][0][0]][0]=y;
		f[x][f[x][0][0]][1]=z;
		f[y][++f[y][0][0]][0]=x;
		f[y][f[y][0][0]][1]=z;
		Max=max(z,Max);
	}
	int l=0,r=Max;
	while(l<r){
		int mid=(l+r)/2;
		if(find(mid))r=mid;
		else l=mid+1;
	}
	printf("%d",l);
}

loading...