建分层图，每一层表示一天的情况
从S向第0层的1号点连边，每层的n向T连INF的边
枚举天数，每多一天就多建一层然后跑最大流，如果当前流量大于人数则输出答案
由于路径长度不会超过n，因此tot个人走这条路径总天数不会超过tot + n，故只需要建tot + n层即可
/**************************************************************
Problem: 1570
User: rausen
Language: C++
Result: Accepted
Time:24 ms
Memory:15936 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
const int N = ;
const int M = ;
const int inf = 1e8; inline int read() {
int x = ;
char ch = getchar();
while (ch < '' || '' < ch)
ch = getchar();
while ('' <= ch && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x;
} struct Edge {
int x, y, z; inline void read_in() {
x = read(), y = read(), z = read();
}
} E[M]; struct edge {
int next, to, f;
edge() {}
edge(int _n, int _t, int _f) : next(_n), to(_t), f(_f) {}
} e[M << ]; int n, m, t;
int S, T, ans;
int first[M], tot = ;
int d[M], q[M]; inline void Add_Edges(int x, int y, int f) {
e[++tot] = edge(first[x], y, f), first[x] = tot;
e[++tot] = edge(first[y], x, ), first[y] = tot;
} #define y e[x].to
#define p q[l]
bool bfs() {
int l, r, x;
memset(d, -, sizeof(d));
d[q[] = S] = ;
for (l = r = ; l != r + ; ++l)
for (x = first[p]; x; x = e[x].next)
if (!~d[y] && e[x].f) {
d[q[++r] = y] = d[p] + ;
if (y == T) return ;
}
return ;
}
#undef p int dfs(int p, int lim) {
if (p == T || !lim) return lim;
int x, tmp, rest = lim;
for (x = first[p]; x && rest; x = e[x].next)
if (d[y] == d[p] + && ((tmp = min(e[x].f, rest)) > )) {
rest -= (tmp = dfs(y, tmp));
e[x].f -= tmp, e[x ^ ].f += tmp;
if (!rest) return lim;
}
if (rest) d[p] = -;
return lim - rest;
}
#undef y int Dinic() {
int res = ;
while (bfs())
res += dfs(S, inf);
return res;
} int main() {
int i, j;
n = read(), m = read(), t = read();
for (i = ; i <= m; ++i) E[i].read_in();
S = , T = ;
Add_Edges(S, , t);
for (i = ; i <= n + t; ++i) {
for (j = ; j <= m; ++j)
Add_Edges(i * n - n + E[j].x + , i * n + E[j].y + , E[j].z);
for (j = ; j <= n; ++j)
Add_Edges(i * n - n + j + , i * n + j + , inf);
Add_Edges(i * n + n + , T, inf);
ans += Dinic();
if (ans == t) {
printf("%d\n", i);
return ;
}
}
}