[文章目录]
Description
约翰正在制造一台新型的挤奶机，但他不希望别人知道．他希望尽可能久地隐藏这个秘密．他把挤奶机藏在他的农场里，使它不被发现．在挤奶机制造的过程中，他需要去挤奶机所在的地方T(1≤T≤200)次．他的农场里有秘密的地道，但约翰只在返回的时候用它．农场被划分成N(2≤N≤200)块区域，用1到200标号．这些区域被P(1≤P≤40000)条道路连接，每条路有一个小于10^6的长度L．两块区域之间可能有多条道路连接．为了减少被发现的可能，约翰不会两次经过农场上的任何一条道路．当然了，他希望走最短的路． 请帮助约翰寻找这T次从仓库走到挤奶机所在地的路线．仓库是区域1，挤奶机所在地是区域N．我们现在要求的是约翰经过的这些道路中最长的路的长度最小是多少，当然他不能重复走某一条路．请注意，我们要求的不是最短的总路程长度，而是所经过的直揍连接两个区域的道路中最长的道路的最小长度． 数据保证约翰可以找到T条没有重复的从仓库到挤奶机所在区域的路．
每条路径只能走一次，所以最大流即为路径条数，然后，我们二分一下答案进行加边就搞定了。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,t;
struct node
{
int v,u,w;
}a[41000];
int head[210],to[81000],nxt[81000],f[81000],cnt=1;
void clear()
{
memset(head,0,sizeof(head)); cnt=1;
}
inline void add(const int x,const int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=1;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=1;
}
int dis[210];
queue<int>q;
bool bfs()
{
memset(dis,-1,sizeof(dis));
while(!q.empty()) q.pop();
q.push(1); dis[1]=0;
while(!q.empty())
{
int x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]<0)
{
dis[to[i]]=dis[x]+1;
if(to[i]==n) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==n) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
bool check(const int x)
{
clear(); int re=0;
for(int i=1;i<=m;i++)
if(a[i].w<=x) add(a[i].v,a[i].u);
while(bfs()) re+=dinic(1,1<<30);
return re>=t;
}
int main()
{
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&a[i].v,&a[i].u,&a[i].w);
int l=1,r=1000001,mid;
while(l<r)
{
mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",r);
return 0;
}