这是一道很有意思的题目。
经过一番化简，我们可以把题目理解为求得最少使所有人都到达的最少时间为 (day) ，同时对于这个时间我们找到了若干条不冲突的方案 (dis_i) 和 (p_i) 表示路径的长度和一批有多少人到达，使得其满足：
[k le sum (k - dis_i + 1) imes p_i
]
化简可得：
[k + sum dis_i imes p_i le k imes sum p_i
]
因此我们只要求得了 (sum p_i) 和 (sum dis_i imes p_i) 就可以快速求得答案。
我们发现他的单位时间内的限制与网络流的流量限制很像，同时 (sum dis_i imes p_i) 又和费用流的费用计算很像，因此我们考虑使用费用流辅助。但是由于总流量不确定，我们考虑枚举总流量。容易发现，在前期费用增长比较缓慢，而后期变化量较大，因此这是一个单峰函数，可以三分。
注意，在三分时，我们要把天数以浮点数形式比较，以防止在向上去整后平台的出现对正确性的影响。（虽然没有任何一个数据卡了这一点）
得到如下代码：
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
template <typename T>
void read(T &x) {
T f=1;x=0;char s=getchar();
while(s<'0'||s>'9') {if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') {x=(x<<3)+(x<<1)+(s^'0');s=getchar();}
x *= f;
}
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
const LL inf = 1e15;
int head[MAXN] , to[MAXM << 1] , nxt[MAXM << 1] , cnt = 1;
LL edge[MAXM << 1] , val[MAXM << 1];
void add(int u , int v , LL c , LL w) {
nxt[++cnt] = head[u];head[u] = cnt;to[cnt] = v;edge[cnt] = c;val[cnt] = w;
nxt[++cnt] = head[v];head[v] = cnt;to[cnt] = u;edge[cnt] = 0;val[cnt] = -w;
}
int las[MAXN] , pre[MAXN] , num , s , t , vis[MAXN];
LL dis[MAXN] , flow[MAXN];
struct MinCostMaxFlow {
LL MaxFlow , MinCost;
bool bfs() {
for (int i = 1; i <= num; ++i) las[i] = 0 , dis[i] = inf , pre[i] = 0 , flow[i] = 0 , vis[i] = 0;
flow[s] = inf , dis[s] = 0;
queue <int> q;q.push(s);
int flag = 0;
while(!q.empty()) {
int x = q.front();
q.pop();
vis[x] = 0;
for (int i = head[x]; i; i = nxt[i]) {
if(!edge[i]) continue;
int v = to[i];
if(dis[v] > dis[x] + val[i]) {
dis[v] = dis[x] + val[i];
flow[v] = min(flow[x] , edge[i]);
pre[v] = x;
las[v] = i;
if(v == t) {
flag = 1;
continue;
}
if(!vis[v]) vis[v] = 1 , q.push(v);
}
}
}
return flag;
}
void MVMC() {
MaxFlow = 0 , MinCost = 0;
while(bfs()) {
int now = t;
MaxFlow += flow[t];
MinCost += dis[t] * flow[t];
while(now != s) {
edge[las[now]] -= flow[t];
edge[las[now] ^ 1] += flow[t];
now = pre[now];
}
}
}
}MIN;
int n , m , k;
double cal(int x) {
for (int i = 2; i <= cnt; i += 2) edge[i] += edge[i ^ 1] , edge[i ^ 1] = 0;
edge[cnt - 1] = x;
MIN.MVMC();
return (k + MIN.MinCost) * 1.0 / MIN.MaxFlow;
}
int main() {
// freopen("snatch.in" , "r" , stdin);
// freopen("snatch.out" , "w" , stdout)
while(scanf("%d %d %d" , &n , &m , &k) != EOF) {
num = n + 2;
s = n + 2 , t = n;
for (int i = 1; i <= m; ++i) {
int u , v , c;
read(u),read(v),read(c);
// u ++ , v ++;
add(u , v , c , 1);
}
if(!k) {
puts("0");
cnt = 1;
for (int i = 1; i <= num; ++i) head[i] = 0;
continue;
}
add(s , 1 , inf , 0);
MIN.MVMC();
if(MIN.MaxFlow == 0) {
puts("No solution");
cnt = 1;
for (int i = 1; i <= num; ++i) head[i] = 0;
continue;
}
int l = 1 , r = MIN.MaxFlow;
LL ans = (k + MIN.MinCost + MIN.MaxFlow - 1) / MIN.MaxFlow - 1;
while(l <= r) {
int mid = (l + r) >> 1;
double ans1 = cal(mid) , ans2 = cal(mid + 1);
if(ans1 > ans2) l = mid + 1 , ans = min(ans , (LL)ceil(ans2));
else r = mid - 1 , ans = min(ans , (LL)ceil(ans1));
}
printf("%lld
" , ans);
cnt = 1;
for (int i = 1; i <= num; ++i) head[i] = 0;
}
return 0;
}