<题目链接>
题目大意：
FJ有N块地，这些地之间有P条双向路，每条路的都有固定的长度l。现在要你找出从第1块地到第n块地的T条不同路径，每条路径上的路段不能与先前的路径重复，问这些路径中的最长路段的最小值是多少。
解题分析：
最小的最大值问题，依然需要用二分答案，枚举出该最大路段的长度，然后将所有小于等于这个值得路段加入网络，将这些路段的容量置为1。因为是无向图，所以正、反向弧的容量都置为1，之后跑一遍最大流，再根据最大流和T的大小关系来判断。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std; #define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
const int N=; struct Edge{
int u,v,c;
}edge[N*N*]; struct Segment{
int a,b,len;
}seg[N*N]; int d[N],cur[N];
int head[N],next[N*N*];
int n,m,k,maxlen,minlen,cnt; void addedge(int u,int v,int w){
edge[cnt].u=u;edge[cnt].v=v,edge[cnt].c=w;
next[cnt]=head[u],head[u]=cnt++; edge[cnt].u=v;edge[cnt].v=u,edge[cnt].c=w;
next[cnt]=head[v],head[v]=cnt++;
} int bfs(int s,int t){
queue<int> q;
mem(d,);
d[s]=;
q.push(s);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i!=-;i=next[i]){
if(edge[i].c> && !d[edge[i].v]){
d[edge[i].v]=d[x]+;
q.push(edge[i].v);
}
}
}
return d[t];
} int dfs(int x,int a){
if(x==n || a==)return a;
int t,f,flow=;
for(int& i=cur[x];i!=-;i=next[i]){
if(d[x]+==d[edge[i].v] && (f=dfs(edge[i].v,min(a,edge[i].c)))>){
edge[i].c-=f;
edge[i^].c+=f;
flow+=f;
a-=f;
if(!a)break;
}
}
return flow;
} int dinic(int s,int t,int limit){
int i,ret=;
while(bfs(s,t)){
for(i=;i<=n;i++)cur[i]=head[i];
ret+=dfs(s,INF);
}
return ret;
} int binary_solve(){
int low=minlen,high=maxlen;
while(low<high){ //这个二分答案部分对格式还是有点疑惑
int mid=(low+high)>>;
cnt=;mem(head,-); //init()
for(int i=;i<m;i++) //加入所有满足要求的边
if(seg[i].len<=mid)
addedge(seg[i].a,seg[i].b,);
int t=dinic(,n,mid);
if(t<k)low=mid+;
else high=mid;
}
return low;
} int main(){
while(~scanf("%d%d%d",&n,&m,&k)){
maxlen=-INF;minlen=INF;
for(int i=;i<m;i++){
scanf("%d%d%d",&seg[i].a,&seg[i].b,&seg[i].len);
maxlen=max(maxlen,seg[i].len);
minlen=min(minlen,seg[i].len);
}
printf("%d\n",binary_solve());
}
return ;
}
2018-11-24