Description：

给一个流量图，每条边长度为 $1$ ，要求每天经过某条边不超过流量，问最少几天可以让 $k$ 个人从一到 $n$ 。

$1\leqslant n\leqslant 1000$

Solution：

首先二分答案，采用类似费用流的思想，每次增广一条最短路，假如说这是第一次，那么显然这条路径能经过的次数是 $mid-d[t]+1$ ，每次经过 $rate[t]$ 这么多人，因此贡献是 $(mid-d[t]+1)\times rate[t]$ ，然后会发现对于之后的路径，这样也是对的，因为计算一下就会发现这个式子刚好可以把退流的那部分正确计算，于是直接把费用流计算答案的那部分改成上面那个式子判断就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,w;

#define MAXN 1010

#define MAXM 5010

struct edge

{

	int to,nxt,f,c;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int f)

{

	e[edgenum] = (edge){b,lin[a],f,1};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0,-1};lin[b] = edgenum++;

	return;

}

int d[MAXN],rate[MAXN],pre[MAXN];

bool inq[MAXN];

int s,t;

bool SPFA()

{

	memset(d,0x3f,sizeof(d));d[s] = 0;

	rate[s] = 0x3f3f3f3f;

	queue<int> q;q.push(s);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		inq[k] = false;

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].c && e[i].f)

			{

				d[e[i].to] = d[k] + e[i].c;

				rate[e[i].to] = min(rate[k],e[i].f);

				pre[e[i].to] = i;

				if(!inq[e[i].to])

				{

					inq[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}//cout << " : " << d[t] << endl;

	return (d[t] != 0x3f3f3f3f);

}

long long flow(int k)

{

	for(int i = t;i != s;i = e[pre[i] ^ 1].to)

	{

		e[pre[i]].f -= rate[t];

		e[pre[i] ^ 1].f += rate[t];

	}

	return 1ll * rate[t] * max(k - d[t] + 1,0);

}

bool check(int k)

{

	for(int i = 0;i < edgenum;i += 2)e[i].f += e[i ^ 1].f,e[i ^ 1].f = 0;

	long long sum = 0;

	while(SPFA())sum += flow(k);//cout << k << " -> " << sum << endl;

	return sum >= w; 

}

int main()

{

	while(~scanf("%d%d%d",&n,&m,&w))

	{

		edgenum = 0; 

		memset(lin,-1,sizeof(lin));

		int a,b,c;

		for(int i = 1;i <= m;++i)

		{

			scanf("%d%d%d",&a,&b,&c);

			++a;++b;

			add(a,b,c);

		}

		s = 1;t = n;

		int l = 0,r = 1000000010,mid;

		while(l < r)

		{

			mid = ((l + r) >> 1);

			if(check(mid))r = mid;

			else l = mid + 1;

		}

		if(l != 1000000010)cout << l << endl;

		else puts("No solution");

	}

	return 0;

}