本文以题解为主。模板传送门。

P2504 [HAOI2006]聪明的猴子

题意

给出 $n$ 个点（ $\le10^3$ ，以坐标形式给出）， $m$ 个询问（ $\le500$ ），问有几个给定的数比这 $n$ 个点的最小生成树的最长边还大。即，求最小瓶颈生成树的瓶颈。

点击查看题解

代码

使用 kruskal 算法可求。由于最小生成树是最小瓶颈生成树的子集，用这个可求它的瓶颈。

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=1000+10,M=N*N,Inf=2147483647;
	const double eps=0.0000001;
	struct edge{int u,v;double len;}e[M*2];
	struct UFDS
	{
		int dad[N],n;
		void init(int p){ n=p; for(int i=1;i<=n;i++) dad[i]=i; }
		int find(int x)
		{  
    		int root=x;  
    		while(root!=dad[root])
        		root=dad[root];
    		return root;  
		}
		void union_(int x,int y)
		{
    		int d1=find(x),d2=find(y);
    		dad[d1]=d2;
    		return;
		}
		bool check(int x,int y)
		{
    		int d1=find(x),d2=find(y);
    		if(d1==d2)
        		return 1;
    		return 0;
		}
	}ufds;
	int cnt=0,n,m,Q,Query[N],x[N],y[N],ret=0;
	double ans=-Inf;
	inline void add(int a,int b,double x){ e[++cnt]=(edge){a,b,x}; }
	bool cmp(edge a,edge b){ return a.len<b.len; }
	void kruskal()
	{
    	int num=0,ru,rv; 
    	sort(e,e+cnt,cmp);
    	for(int i=1;i<=m;i++)
    	{
       		ru=ufds.find(e[i].u),rv=ufds.find(e[i].v);
        	if(ru==rv)
            	continue;
        	ans=(e[i].len-ans>eps?e[i].len:ans);
			ufds.union_(ru,rv);
        	if(++num==n-1)
            	break;
    	}
	}	
	void yzmain()
	{
		scanf("%d",&Q);
		for(int i=1;i<=Q;i++) scanf("%d",Query+i);
		scanf("%d",&n);m=n*n;ufds.init(n);
		for(int i=1;i<=n;i++) scanf("%d%d",x+i,y+i);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				add(i,j,sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));
		kruskal();
		for(int i=1;i<=Q;i++) if(ans-Query[i]<eps) ret++;
	    printf("%d\n",ret);
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

P1396 营救

题意

1 万个点，2 万个边，给定两点，求它们之间的一条路径，令路径上的最大边权最小。输出此路径最大边权。即，求两点最小瓶颈路的瓶颈。

点击查看题解

题解

二分答案

~~看，这个题面很二分！~~

单调性分析：屏蔽的边越多，越容易使得图上两点不连通，反之越容易连通。

我们对边权进行二分，每次 check 时从开始点进行遍历，屏蔽比 mid 大的边，判断给定的两点是否连通。

代码见命名空间 2。

最小生成树

构建最小生成树，按这棵树建新图，在这个图上随便搜索一下即可。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz1//求最小瓶颈路
{
	const int M=20000+10,N=10000+10;
	struct Road{int u,v,len;}road[M];
	struct Graph
	{
		struct edge{int nxt,to,len;}e[M*2];
		int head[N],cnt;
		Graph(){memset(head,0,sizeof(head));cnt=0;}
		void add(int a,int b,int c){e[++cnt]=(edge){head[a],b,c};head[a]=cnt;}
	}Tree;
	struct UFDS
	{
		int dad[M],n;
		void init(int p){ n=p; for(int i=1;i<=n;i++) dad[i]=i; }
		int find(int x)
		{  
    		int root=x;  
    		while(root!=dad[root])
        		root=dad[root];
    		return root;  
		}
		void union_(int x,int y)
		{
    		int d1=find(x),d2=find(y);
    		dad[d1]=d2;
    		return;
		}
		bool check(int x,int y)
		{
    		int d1=find(x),d2=find(y);
    		if(d1==d2)
        		return 1;
    		return 0;
		}
	}ufds;
	int n,m,s,t,ans=0,pos=0,stk[N];
	bool cmp(Road a,Road b){ return a.len<b.len; }
	void kruskal()
	{
    	int num=0,ru,rv; 
    	sort(road+1,road+m+1,cmp);
    	for(int i=1;i<=m;i++)
    	{
       		ru=ufds.find(road[i].u),rv=ufds.find(road[i].v);
        	if(ru==rv)
            	continue;
			Tree.add(road[i].u,road[i].v,road[i].len);
			Tree.add(road[i].v,road[i].u,road[i].len);
			ufds.union_(ru,rv);
        	if(++num==n-1)
            	break;
    	}
	}
	void dfs(int root,int dad)
	{
		if(root==t) 
		{
			for(int i=1;i<=pos;i++)
				ans=max(ans,stk[i]);
			return;
		}
		for(int i=Tree.head[root];i;i=Tree.e[i].nxt)
		{
			int son=Tree.e[i].to,len=Tree.e[i].len;
			if(son==dad) continue;
			stk[++pos]=len;
			dfs(son,root);
			pos--;
		}
	}
	void yzmain()
	{
		int ta,tb,tc;
		scanf("%d%d%d%d",&n,&m,&s,&t);
		for(int i=1;i<=m;i++)
			scanf("%d%d%d",&ta,&tb,&tc),
			road[i]=(Road){ta,tb,tc};
		ufds.init(n);kruskal();
		dfs(s,s);
		printf("%d\n",ans);
		return;
	}
}
namespace _yz2//二分答案
{
    const int M=20000+10,N=10000+10;
	struct Graph
	{
		struct edge{int nxt,to,len;}e[M*2];
		int head[N],cnt;
		Graph(){memset(head,0,sizeof(head));cnt=0;}
		void add(int a,int b,int c){e[++cnt]=(edge){head[a],b,c};head[a]=cnt;}
	}G;
	int n,m,s,t,ans=0,val[M],v[N];
	void dfs(int root,int gate)
	{
		v[root]=1;
		for(int i=G.head[root];i;i=G.e[i].nxt)
		{
			int son=G.e[i].to,len=G.e[i].len;
			if(v[son] || len>gate) continue;
			dfs(son,gate);
		}
	}
	int check(int mid)
	{
		memset(v,0,sizeof(v));
		dfs(s,mid);
		return v[t];
	}
	void yzmain()
	{
		int ta,tb,tc,l,r;
		scanf("%d%d%d%d",&n,&m,&s,&t);
		l=0,r=m+1;
		for(int i=1;i<=m;i++)
			scanf("%d%d%d",&ta,&tb,&tc),val[i]=tc,
			G.add(ta,tb,tc),G.add(tb,ta,tc);
		sort(val+1,val+m+1);val[m+1]=2147483647;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(check(val[mid])) ans=val[mid],r=mid-1;
			else l=mid+1;	
		}
		printf("%d\n",ans);
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz2::yzmain();
	return 0;
}