这道题三种方法我均尝试了一波。总体而言,最小生成树的解法最快,二分加并查集次之,二分加搜索最慢。
因为点数很小,所以存边直接开的邻接矩阵。如果使用邻接表,每次二分后check的时间会优化到$O(m)$
解法1 最小生成树
需要搞清怎么得到最大值最小的树边,就这个问题和队友讨论了一早上,最终得到了一个不严谨的证明。
我们使用kruskal算法时,将边从小到大排序。
假设我们构造连通块时使用的最后一条边的编号为d,则d之左边的所有边一定可以使得所有点练成一个连通块。
如果kruskal算法求得的d不是最大值最小的边,则应该存在这样的情形
$小边+超大边=中边+大边$ 即$a+d=b+c$。
考虑kruskal中每条边的功能,每条边最多可以沟通2条连通块。则边d必定可以被c或b替换,使得解更优(这种情况自然是不存在的,kruskal执行的过程中会先将b或者c加入而忽略d)。
ac代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#define pdd pair<double,double>
#define F first
#define S second
using namespace std;
const int N=310,M=8010;
int ufs[N];
int find(int i){
if(ufs[i]!=i)
ufs[i]=find(ufs[i]);
return ufs[i];
}
void merge(int i,int j){
i=find(i);
j=find(j);
ufs[i]=j;
}
int n,m;
struct edge{
int a,b,w;
};
edge mifune[M];
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
ufs[i]=i;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&mifune[i].a,&mifune[i].b,&mifune[i].w);
}
sort(mifune+1,mifune+1+m,[](edge e1,edge e2){
return e1.w<e2.w;
});
int res=0;
for(int i=1;i<=m;i++){
int a=mifune[i].a,b=mifune[i].b,w=mifune[i].w;
if(find(a)==find(b))
continue;
else{
res=w;
merge(a,b);
}
}
cout<<n-1<<" "<<res;
}
解法2 二分+并查集
check时比较每个点的根节点即可
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<queue>
#include<vector>
#define pdd pair<double,double>
#define F first
#define S second
using namespace std;
const int N=310,M=8010,INF=0x3f3f3f3f;
int n,m;
int ufs[N];
int find(int i){
if(ufs[i]!=i)
ufs[i]=find(ufs[i]);
return ufs[i];
}
void merge(int i, int j){
i=find(i);
j=find(j);
ufs[i]=j;
}
struct edge{
int a,b,w;
};
edge mifune[M];
bool check(int x){
for(int i=1;i<=n;i++){
ufs[i]=i;
}
for(int i=1;i<=m;i++){
if(mifune[i].w<=x){
merge(mifune[i].a,mifune[i].b);
}
}
int target=find(1);
for(int i=1;i<=n;i++){
if(target!=find(i))
return false;
}
return true;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d %d %d",&mifune[i].a,&mifune[i].b,&mifune[i].w);
}
int lo=1,hi=10012,mi;
while(lo<=hi){
mi=(lo+hi)>>1;
if(check(mi))
hi=mi-1;
else lo=mi+1;
}
cout<<n-1<<" "<<lo;
}
解法3 二分+bfs
比较慢,原因是使用邻接矩阵每个点都会遍历到,使用邻接表会更快
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<queue>
#include<vector>
#define pdd pair<double,double>
#define F first
#define S second
using namespace std;
const int N=310,M=8010,INF=0x3f3f3f3f;
int n,m;
int g[N][N];
bool st[N];
bool check(int x){
memset(st,false,sizeof st);
queue<int>q;
q.push(1);
while(!q.empty()){
int t=q.front();
q.pop();
st[t]=true;
for(int i=1;i<=n;i++){
if(!st[i]&&g[t][i]<=x)
{
q.push(i);
}
}
}
for(int i=1;i<=n;i++)
if(!st[i])
return false;
return true;
}
int main(){
scanf("%d %d",&n,&m);
int a,b,w;
memset(g,0x3f,sizeof g);
for(int i=1;i<=m;i++) {
scanf("%d %d %d", &a, &b, &w);
g[a][b] = g[b][a] = min(g[a][b], w);
}
int lo=1,hi=10001,mi;
while(lo<=hi){
mi=(lo+hi)>>1;
if(check(mi))
hi=mi-1;
else lo=mi+1;
}
cout<<n-1<<" "<<lo;
}