# Hdu-4807-lunch time (dichotomy + fee flow, thinking)

Main idea: n points, m sides, k individuals from point 0 to point n-1. The digraph (not mentioned in the title) has a length of 1 for each side, which has the maximum flow capacity. People's speed is 1. Ask everyone to arrive at n-1.

Thought: at the beginning, I thought it was the biggest flow. I wrote a board and found that there was still a speed limit..

Call the length the cost. Run the cost stream once, and record the residual network for each. (it means the number of people who can arrive at different times). Then two minutes.

Control the maximum time consumption. Divide the first time that meets the requirements, and this time is ans.

The condition of dichotomy is that all traffic control consumed before mid in all time will get comprehensive number of people and judge whether the number of people can reach n-1 is more than k.

ACCode:

``` // luogu-judger-enable-o2

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<time.h>

#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;

#define ll long long
#define Pair pair<int,int>
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a)) / / watermark
//std::ios::sync_with_stdio(false);
//  register
const int MAXN=3e3+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll mod=192600817;
const double EPS=1.0e-8;
const double PI=acos(-1.0);

struct Node1{
int v,w,cost,nxt;
Node1(int _v=0,int _w=0,int _cost=0,int _nxt=0){
v=_v;w=_w;cost=_cost;nxt=_nxt;
}
};
struct Node2{
ll cost,flow;
Node2(ll _cost=0,ll _flow=0){
cost=_cost;flow=_flow;
}
};
Node2 Ans[MAXN];
Node1 Edge[MAXN<<2];
int Pre[MAXN],Dis[MAXN],Flow[MAXN],Last[MAXN];
int Vis[MAXN];
int maxw,Cnt;
int n,m,k,S,T;

void Intt(){
maxw=0;Cnt=0;
}
void Add(int u,int v,int w,int cost){
}
int SPFA(){
clean(Vis,0);Vis[S]=1;
clean(Dis,INF32);Dis[S]=0;
Flow[S]=INF32;Pre[T]=-1;
queue<int> que;que.push(S);
while(que.size()){
int u=que.front();que.pop();
Vis[u]=0;
int temp=Edge[i].v;
if(Edge[i].w>0&&Dis[temp]>Dis[u]+Edge[i].cost){
Dis[temp]=Dis[u]+Edge[i].cost;
Flow[temp]=min(Flow[u],Edge[i].w);
Last[temp]=i;
Pre[temp]=u;
if(Vis[temp]==0){
Vis[temp]=1;que.push(temp);
}
}
}
}return Dis[T]==INF32?0:1;
}
void MCMF(){
while(SPFA()){
//        cout<<Cnt<<" "<<Dis[T]<<endl;
int u=T;Cnt++;
maxw+=Flow[T];
Ans[Cnt]=Node2(Dis[T],Flow[T]);
while(u!=S){
Edge[Last[u]].w-=Flow[T];
Edge[Last[u]^1].w+=Flow[T];
u=Pre[u];
}
}
}
ll Judge(ll mid){//Spend up to mid time walking
ll tot=0;
for(int i=1;i<=Cnt;++i){
if(Ans[i].cost<=mid){
tot+=Ans[i].flow*(mid-Ans[i].cost+1);
}
}
int main(){
while(~scanf("%d%d%d",&n,&m,&k)){
int a,b,w;Intt();
for(int i=1;i<=m;++i){
scanf("%d%d%d",&a,&b,&w);
}S=0;T=n-1;
if(k==0){
printf("0\n");continue;
}MCMF();
//        cout<<1<<endl;
if(maxw==0){
printf("No solution\n");continue;
}ll l=1,r=1e9,mid;
//        for(int i=1;i<=Cnt;++i){
//            cout<<Ans[i].cost<<" "<<Ans[i].flow<<endl;
//        }