城市

题目描述
N(2<=n<=200)个城市，M(1<=m<=40000)条无向边，你要找T(1<=T<=200)条从城市1到城市N的路，使得最长的边的长度最小，边不能重复用。

输入格式
第1行三个整数N,M,T用空格隔开。

第2行到P+1行，每行包括三个整数Ai,Bi,Li表示城市Ai到城市Bi之间有一条长度为Li的道路。

输出格式
输出只有一行，包含一个整数，即经过的这些道路中最长的路的最小长度。

输入输出样例
输入 #1复制
7 9 2
1 2 2
2 3 5
3 7 5
1 4 1
4 3 1
4 5 7
5 7 1
1 6 3
6 7 3
输出 #1复制
5

看到题目的最大的最小，应该不难想到二分。

但是二分怎么check呢？怎么快速判断当前的mid是否和法呢？

可能因为自己对网络流比较收悉吧，看到T条路，然后我们就想到了网络流的流量，我们每次重新加边，加小于等于mid的边，就可以保证一定不会有大于mid的边权了，然后判断最大流是否大于t。若大于t就是有解的，不然就无解，改变二分区间。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=210,M=16e4+10;
int n,m,t,h[N],a[M],b[M],c[M];
int head[N],nex[M],to[M],w[M],tot;
inline void ade(int a,int b,int c){
	to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c){
	ade(a,b,c);	ade(b,a,0);
}
int bfs(){
	memset(h,0,sizeof h);	queue<int> q;	q.push(1);	h[1]=1;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(w[i]&&!h[to[i]]){
				h[to[i]]=h[u]+1;	q.push(to[i]);
			}
		}
	}
	return h[n];
}
int dfs(int x,int f){
	if(x==n)	return f;	int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(w[i]&&h[to[i]]==h[x]+1){
			int mi=dfs(to[i],min(w[i],f));
			w[i]-=mi;	w[i^1]+=mi;	fl+=mi;	f-=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;
}
int dinic(){
	int res=0;
	while(bfs())	res+=dfs(1,inf);
	return res;
}
inline int check(int mid){
	memset(head,0,sizeof head);	tot=1;
	for(int i=1;i<=m;i++)	if(c[i]<=mid)	add(a[i],b[i],1),add(b[i],a[i],1);
	return dinic()>=t;
}
int bsearch(){
	int l=1,r=100000;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid))	r=mid;
		else	l=mid+1;
	}
	return l;
}
int main(){
	cin>>n>>m>>t;
	for(int i=1;i<=m;i++)	cin>>a[i]>>b[i]>>c[i];
	cout<<bsearch()<<endl;
	return 0;
}