题目描述：

F个地区，p条小道路（每条小道路a,b,c,表示从a到b需要时间c）.

给你一个数T。

让你在1地区和F地区之间找到T个不同的路径（就是每个路径没有重合条小道路）

让这T个路径中的最长的小道路最短，求这个最短值。

解题报告：

二分枚举最短值mid。

点1~F，如果小道路时间c <= mid，则连接a到b，容量为1。

源点s = 0；

连接s和1，容量为T。

汇点就是最后一个地区F。

如果最大流等于T，那么这个mid合法。

（这样的最大流就是从1到F不同路径的数目，很好理解）

代码如下：

#include<iostream>
using namespace std;
#define Max 0x7fffffff
#define size 210
struct edge{int from, to, val, next;}e[10000000];
int v[size], que[size], dis[size], cnt, cur[size];;
void insert(int from, int to, int va)
{
    e[cnt].from = from, e[cnt].to = to; e[cnt].val = va;
    e[cnt].next = v[from];v[from] = cnt++;
    e[cnt].from = to, e[cnt].to = from; e[cnt].val = 0;
    e[cnt].next = v[to];v[to] = cnt++;
}
bool bfs(int n, int s, int t)
{
    int head, tail, id;
    head = tail = 0; que[tail++] = s;
    memset(dis, -1, sizeof(int) * n);dis[s] = 0;
    while(head < tail) // bfs,得到顶点i的距s的最短距离dis[i]
        for(id = v[que[head++]]; id != -1; id = e[id].next)
            if (e[id].val > 0 && dis[e[id].to] == -1)
            {
                dis[e[id].to] = dis[e[id].from] + 1;
                que[tail++] = e[id].to;
                if (e[id].to == t) return true;
            }
    return false;
}

int Dinic(int n, int s, int t)
{
    int maxflow = 0, tmp, i;
    while(bfs(n, s, t))
    {
        int u = s, tail = 0;
        for(i = 0; i < n; i++) cur[i] = v[i];
        while(cur[s] != -1)
            if (u != t && cur[u] != -1 && e[cur[u]].val > 0 && dis[u] != -1 && dis[u] + 1 == dis[e[cur[u]].to])
            {que[tail++] = cur[u]; u = e[cur[u]].to;}
            else if (u == t)
            {
                for(tmp = Max, i = tail - 1; i >= 0; i--) tmp = min(tmp, e[que[i]].val);
                for(maxflow += tmp, i = tail - 1; i >= 0; i--)
                {
                    e[que[i]].val -= tmp;
                    e[que[i] ^ 1].val += tmp;
                    if (e[que[i]].val == 0) tail = i;
                }
                u = e[que[tail]].from;
            }
            else
            {
                while(tail > 0 && u != s && cur[u] == -1) u = e[que[--tail]].from;
                cur[u] = e[cur[u]].next;
            }
    }
    return maxflow;
}
int n, p, T, ee[40001][3], s, t, ans;
void jeogia(int mmax)
{
    int l = 0, r = mmax;
    s = 0, t = n; ans = 0x7fffffff;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        memset(v, -1, sizeof(v)); cnt = 0;
        insert(s, 1, T);
        for(int i = 0; i < p; i++)
            if (ee[i][2] <= mid)
            {
                insert(ee[i][0], ee[i][1], 1);
                insert(ee[i][1], ee[i][0], 1);
            }
        if (Dinic(n + 1, s, t) >= T)
        {
            if (mid < ans) ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
}
int main()
{
    while(scanf("%d%d%d", &n, &p, &T) != EOF)
    {
        int mmax = -1;
        for(int i = 0; i < p; i++)
        {
            scanf("%d%d%d", &ee[i][0], &ee[i][1], &ee[i][2]);
            if (ee[i][2] > mmax) mmax = ee[i][2];
        }
        jeogia(mmax);
        printf("%d\n", ans);

    }
    return 0;
}