题意：
给一图，，求从点1到n的t条边不相交的路径，目标是最小化最t条路径中的最大边，输出该最大边。
分析：
求最值的问题满足单调性都可以用二分来做，二分是加速的枚举方法。这题二分枚举最大边建图，每次用长度小于等于二分值的边建图并置容量为1，求最大流即可。
代码：
//poj 2455//sep9#include <iostream>#include <queue>#include <algorithm>using namespace std;const int maxN=256;const int maxM=40012;struct Edge{int v,f,nxt;}e[maxM*2+10];queue<int> que;int src,sink;int g[maxN+10];int nume;bool vis[maxN+10];int dist[maxN+10];int n,p,t;int a[maxM],b[maxM],c[maxM];void addedge(int u,int v,int c){e[++nume].v=v;e[nume].f=c;e[nume].nxt=g[u];g[u]=nume;e[++nume].v=u;e[nume].f=c;e[nume].nxt=g[v];g[v]=nume;}void init(){memset(g,0,sizeof(g));nume=1;}int bfs(){while(!que.empty()) que.pop();memset(dist,0,sizeof(dist));memset(vis,0,sizeof(vis));vis[src]=true;que.push(src);while(!que.empty()){int u=que.front();que.pop();for(int i=g[u];i;i=e[i].nxt)if(e[i].f&&!vis[e[i].v]){que.push(e[i].v);dist[e[i].v]=dist[u]+1;vis[e[i].v]=true;if(e[i].v==sink)return 1;}}return 0;}int dfs(int u,int delta){if(u==sink)return delta;int ret=0;for(int i=g[u];ret<delta&&i;i=e[i].nxt)if(e[i].f&&dist[e[i].v]==dist[u]+1){int dd=dfs(e[i].v,min(e[i].f,delta-ret));if(dd>0){e[i].f-=dd;e[i^1].f+=dd;ret+=dd;}elsedist[e[i].v]=-1;}return ret;}int dinic(){int ret=0;while(bfs()==1)ret+=dfs(src,INT_MAX);return ret;}bool check(int mid){init();src=0,sink=n+1;for(int i=0;i<p;++i)if(c[i]<=mid)addedge(a[i],b[i],1);addedge(src,1,t);addedge(n,sink,t);if(dinic()==t)return true;return false;}int main(){ scanf("%d%d%d",&n,&p,&t);int maxl=-1;for(int i=0;i<p;++i){scanf("%d%d%d",&a[i],&b[i],&c[i]);maxl=max(maxl,c[i]);}int l=0,r=maxl+1,ans;while(l<r){int mid=(l+r)/2;if(check(mid))r=mid,ans=mid;elsel=mid+1;}printf("%d",ans);return 0;}
青春在我的心中是苦涩的又是甘甜的，是精致的又是粗糙的，
