泛做题记录

const int N = 205;
const int M = 8e4 + 5;
const int inf = 2147483647;

int head[N], ver[M], _edge[M], Next[M], tot = 1;
int n, p, T, d[N], now[N], s, t;
queue<int> que;
int edge[M];

void add(int u, int v, int w) {
  ver[++tot] = v, _edge[tot] = w;
  Next[tot] = head[u], head[u] = tot;
}

bool bfs() {
  memset(d, 0, sizeof d);
  while (que.size()) que.pop();
  d[s] = 1, que.push(s), now[s] = head[s];

  while (que.size()) {
    int u = que.front(); que.pop();

    for (int i = head[u]; i; i = Next[i]) {
      int v = ver[i], w = edge[i];
      if (w && !d[v]) {
        d[v] = d[u] + 1;
        now[v] = head[v];
        if (v == t) return 1;
        que.push(v);
      }
    }
  }

  return 0;
}

int dfs(int u, int f) {
  if (u == t || !f) return f;
  int res = 0;

  for (int &i = now[u]; i; i = Next[i]) {
    if (edge[i] && d[ver[i]] == d[u] + 1) {
      int k = dfs(ver[i], min(f, edge[i]));
      if (!k) d[ver[i]] = 0;
      edge[i] -= k, edge[i ^ 1] += k;
      f -= k, res += k;
      if (f <= 0) break;
    }
  }

  return res;
}

int dinic() {
  int res = 0, f;
  while (bfs()) while (f = dfs(s, inf)) res += f;
  return res;
}

bool check(int val) {
  LF(i, 2, tot) edge[i] = (_edge[i] <= val ? 1 : 0);
  if (dinic() >= T) return 1;
  return 0;
}

int main() {
  cin >> n >> p >> T;
  s = 1, t = n;

  LF(i, 1, p) {
    int u, v, w; cin >> u >> v >> w;
    add(u, v, w);
    add(v, u, w);
  }

  int l = 1, r = 1e6;

  while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid)) r = mid;
    else l = mid + 1;
  }

  cout << l;
  return 0;
}