题目链接：
题目分析
直接二分这个最大边的边权，然后用最大流判断是否可以有 T 的流量。
代码
#include#include #include #include #include #include using namespace std; const int MaxN = 200 + 5, MaxM = 80000 + 5, INF = 999999999; inline int gmin(int a, int b) {return a < b ? a : b;}inline int gmax(int a, int b) {return a > b ? a : b;} int n, m, Ts, Top, Ans, S, T, Tot;int d[MaxN], Num[MaxN]; struct Edge{ int u, v, w, len; Edge *Next, *Other;} E[MaxM * 2], *P = E, *Point[MaxN], *Last[MaxN], *EA[MaxM]; inline void AddEdge(int x, int y, int z){ Edge *Q = ++P; ++P; EA[++Top] = P; P -> u = x; P -> v = y; P -> len = z; P -> Next = Point[x]; Point[x] = P; P -> Other = Q; Q -> u = y; Q -> v = x; Q -> len = z; Q -> Next = Point[y]; Point[y] = Q; Q -> Other = P; } void Set_Edge(int x){ for (int i = 1; i <= Top; ++i) { if (EA[i] -> len <= x) EA[i] -> w = 1; else EA[i] -> w = 0; EA[i] -> Other -> w = 0; }} int DFS(int Now, int Flow){ if (Now == T) return Flow; int ret = 0; for (Edge *j = Last[Now]; j; j = j -> Next) if (j -> w && d[j -> u] == d[j -> v] + 1) { Last[Now] = j; int p = DFS(j -> v, gmin(j -> w, Flow - ret)); j -> w -= p; j -> Other -> w += p; ret += p; if (ret == Flow) return ret; } if (d[S] >= Tot) return ret; if (--Num[d[Now]] == 0) d[S] = Tot; ++Num[++d[Now]]; Last[Now] = Point[Now]; return ret; } bool Check(){ int MaxFlow = 0; S = 1; T = n; Tot = n; memset(d, 0, sizeof(d)); memset(Num, 0, sizeof(Num)); Num[0] = Tot; for (int i = 1; i <= Tot; ++i) Last[i] = Point[i]; while (d[S] < Tot) MaxFlow += DFS(S, INF); if (MaxFlow >= Ts) return true; else return false;} int main(){ scanf("%d%d%d", &n, &m, &Ts); int a, b, c; int l, r, mid; l = INF; r = -INF; Top = 0; for (int i = 1; i <= m; ++i) { scanf("%d%d%d", &a, &b, &c); AddEdge(a, b, c); AddEdge(b, a, c); l = gmin(l, c); r = gmax(r, c); } while (l <= r) { mid = (l + r) >> 1; Set_Edge(mid); if (Check()) { Ans = mid; r = mid - 1; } else l = mid + 1; } printf("%d\n", Ans); return 0;}